...
Run Format

Source file 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.
  //
  // This was originally based on tcmalloc, but has diverged quite a bit.
  // 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 70 size classes, each of which
  // has its own free set 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 a free bitmap.
  //
  // The allocator's data structures are:
  //
  //	fixalloc: a free-list allocator for fixed-size off-heap objects,
  //		used to manage storage used by the allocator.
  //	mheap: the malloc heap, managed at page (8192-byte) granularity.
  //	mspan: a run of pages managed by the mheap.
  //	mcentral: collects all spans of a given size class.
  //	mcache: a per-P cache of mspans with free space.
  //	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 mspan in this P's mcache.
  //	   Scan the mspan's free bitmap to find a free slot.
  //	   If there is a free slot, allocate it.
  //	   This can all be done without acquiring a lock.
  //
  //	2. If the mspan has no free slots, obtain a new mspan
  //	   from the mcentral's list of mspans of the required size
  //	   class that have free space.
  //	   Obtaining a whole span amortizes the cost of locking
  //	   the mcentral.
  //
  //	3. If the mcentral's mspan list is empty, obtain a run
  //	   of pages from the mheap to use for the mspan.
  //
  //	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.
  //
  // Sweeping an mspan and freeing objects on it proceeds up a similar
  // hierarchy:
  //
  //	1. If the mspan is being swept in response to allocation, it
  //	   is returned to the mcache to satisfy the allocation.
  //
  //	2. Otherwise, if the mspan still has allocated objects in it,
  //	   it is placed on the mcentral free list for the mspan's size
  //	   class.
  //
  //	3. Otherwise, if all objects in the mspan are free, the mspan
  //	   is now "idle", so it is returned to the mheap and no longer
  //	   has a size class.
  //	   This may coalesce it with adjacent idle mspans.
  //
  //	4. If an mspan remains idle for long enough, return its pages
  //	   to the operating system.
  //
  // Allocating and freeing a large object uses the mheap
  // directly, bypassing the mcache and mcentral.
  //
  // Free object slots in an mspan are zeroed only if mspan.needzero is
  // false. If needzero is true, objects are zeroed as they are
  // allocated. There are various benefits to delaying zeroing this way:
  //
  //	1. Stack frame allocation can avoid zeroing altogether.
  //
  //	2. It exhibits better temporal locality, since the program is
  //	   probably about to write to the memory.
  //
  //	3. We don't zero pages that never get reused.
  
  package runtime
  
  import (
  	"runtime/internal/sys"
  	"unsafe"
  )
  
  const (
  	debugMalloc = false
  
  	maxTinySize   = _TinySize
  	tinySizeClass = _TinySizeClass
  	maxSmallSize  = _MaxSmallSize
  
  	pageShift = _PageShift
  	pageSize  = _PageSize
  	pageMask  = _PageMask
  	// By construction, single page spans of the smallest object class
  	// have the most objects per span.
  	maxObjsPerSpan = pageSize / 8
  
  	mSpanInUse = _MSpanInUse
  
  	concurrentSweep = _ConcurrentSweep
  
  	_PageSize = 1 << _PageShift
  	_PageMask = _PageSize - 1
  
  	// _64bit = 1 on 64-bit systems, 0 on 32-bit systems
  	_64bit = 1 << (^uintptr(0) >> 63) / 2
  
  	// 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 - sys.PtrSize/4*sys.GoosWindows - 1*sys.GoosPlan9
  
  	// 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.
  	// The only exception is mips32 which only has access to low 2GB of virtual memory.
  	// 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*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))
  	_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
  
  	_MaxArena32 = 1<<32 - 1
  
  	// minLegalPointer is the smallest possible legal pointer.
  	// This is the smallest possible architectural page size,
  	// since we assume that the first page is never mapped.
  	//
  	// This should agree with minZeroPage in the compiler.
  	minLegalPointer uintptr = 4096
  )
  
  // physPageSize is the size in bytes of the OS's physical pages.
  // Mapping and unmapping operations must be done at multiples of
  // physPageSize.
  //
  // This must be set by the OS init code (typically in osinit) before
  // mallocinit.
  var physPageSize uintptr
  
  // 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() {
  	if class_to_size[_TinySizeClass] != _TinySize {
  		throw("bad TinySizeClass")
  	}
  
  	testdefersizes()
  
  	// Copy class sizes out for statistics table.
  	for i := range class_to_size {
  		memstats.by_size[i].size = uint32(class_to_size[i])
  	}
  
  	// Check physPageSize.
  	if physPageSize == 0 {
  		// The OS init code failed to fetch the physical page size.
  		throw("failed to get system page size")
  	}
  	if physPageSize < minPhysPageSize {
  		print("system page size (", physPageSize, ") is smaller than minimum page size (", minPhysPageSize, ")\n")
  		throw("bad system page size")
  	}
  	if physPageSize&(physPageSize-1) != 0 {
  		print("system page size (", physPageSize, ") must be a power of 2\n")
  		throw("bad system page size")
  	}
  
  	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 2 bits per allocated word.
  	if sys.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 / (sys.PtrSize * 8 / 2)
  		spansSize = arenaSize / _PageSize * sys.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 the entire 4GB address space (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.
  
  		// 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.
  		// In the worst case, fall back to a 0-sized initial arena,
  		// in the hope that subsequent reservations will succeed.
  		arenaSizes := []uintptr{
  			512 << 20,
  			256 << 20,
  			128 << 20,
  			0,
  		}
  
  		for _, arenaSize := range arenaSizes {
  			bitmapSize = (_MaxArena32 + 1) / (sys.PtrSize * 8 / 2)
  			spansSize = (_MaxArena32 + 1) / _PageSize * sys.PtrSize
  			if limit > 0 && arenaSize+bitmapSize+spansSize > limit {
  				bitmapSize = (limit / 9) &^ ((1 << _PageShift) - 1)
  				arenaSize = bitmapSize * 8
  				spansSize = arenaSize / _PageSize * sys.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)
  
  	spansStart := p1
  	mheap_.bitmap = p1 + spansSize + bitmapSize
  	if sys.PtrSize == 4 {
  		// Set arena_start such that we can accept memory
  		// reservations located anywhere in the 4GB virtual space.
  		mheap_.arena_start = 0
  	} else {
  		mheap_.arena_start = p1 + (spansSize + bitmapSize)
  	}
  	mheap_.arena_end = p + pSize
  	mheap_.arena_used = p1 + (spansSize + bitmapSize)
  	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(spansStart, spansSize)
  	_g_ := getg()
  	_g_.m.mcache = allocmcache()
  }
  
  // sysAlloc allocates the next n bytes from the heap arena. The
  // returned pointer is always _PageSize aligned and between
  // h.arena_start and h.arena_end. sysAlloc returns nil on failure.
  // There is no corresponding free function.
  func (h *mheap) sysAlloc(n uintptr) unsafe.Pointer {
  	if n > h.arena_end-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 // Careful: can overflow
  		if h.arena_end <= new_end && new_end-h.arena_start-1 <= _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
  			}
  			// p can be just about anywhere in the address
  			// space, including before arena_end.
  			if p == h.arena_end {
  				h.arena_end = new_end
  				h.arena_reserved = reserved
  			} else if h.arena_end < p && p+p_size-h.arena_start-1 <= _MaxArena32 {
  				// Keep everything page-aligned.
  				// Our pages are bigger than hardware pages.
  				h.arena_end = p + p_size
  				used := p + (-p & (_PageSize - 1))
  				h.mapBits(used)
  				h.mapSpans(used)
  				h.arena_used = used
  				h.arena_reserved = reserved
  			} else {
  				// We got a mapping, but it's not
  				// linear with our current arena, so
  				// we can't use it.
  				//
  				// TODO: Make it possible to allocate
  				// from this. We can't decrease
  				// arena_used, but we could introduce
  				// a new variable for the current
  				// allocation position.
  
  				// We haven't added this allocation to
  				// the stats, so subtract it from a
  				// fake stat (but avoid underflow).
  				stat := uint64(p_size)
  				sysFree(unsafe.Pointer(p), p_size, &stat)
  			}
  		}
  	}
  
  	if n <= h.arena_end-h.arena_used {
  		// Keep taking from our reservation.
  		p := h.arena_used
  		sysMap(unsafe.Pointer(p), n, h.arena_reserved, &memstats.heap_sys)
  		h.mapBits(p + n)
  		h.mapSpans(p + n)
  		h.arena_used = p + n
  		if raceenabled {
  			racemapshadow(unsafe.Pointer(p), n)
  		}
  
  		if 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 h.arena_end-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.
  	p_size := round(n, _PageSize) + _PageSize
  	p := uintptr(sysAlloc(p_size, &memstats.heap_sys))
  	if p == 0 {
  		return nil
  	}
  
  	if p < h.arena_start || p+p_size-h.arena_start > _MaxArena32 {
  		top := ^uintptr(0)
  		if top-h.arena_start-1 > _MaxArena32 {
  			top = h.arena_start + _MaxArena32 + 1
  		}
  		print("runtime: memory allocated by OS (", hex(p), ") not in usable range [", hex(h.arena_start), ",", hex(top), ")\n")
  		sysFree(unsafe.Pointer(p), p_size, &memstats.heap_sys)
  		return nil
  	}
  
  	p_end := p + p_size
  	p += -p & (_PageSize - 1)
  	if p+n > h.arena_used {
  		h.mapBits(p + n)
  		h.mapSpans(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 p&(_PageSize-1) != 0 {
  		throw("misrounded allocation in MHeap_SysAlloc")
  	}
  	return unsafe.Pointer(p)
  }
  
  // base address for all 0-byte allocations
  var zerobase uintptr
  
  // nextFreeFast returns the next free object if one is quickly available.
  // Otherwise it returns 0.
  func nextFreeFast(s *mspan) gclinkptr {
  	theBit := sys.Ctz64(s.allocCache) // Is there a free object in the allocCache?
  	if theBit < 64 {
  		result := s.freeindex + uintptr(theBit)
  		if result < s.nelems {
  			freeidx := result + 1
  			if freeidx%64 == 0 && freeidx != s.nelems {
  				return 0
  			}
  			s.allocCache >>= (theBit + 1)
  			s.freeindex = freeidx
  			v := gclinkptr(result*s.elemsize + s.base())
  			s.allocCount++
  			return v
  		}
  	}
  	return 0
  }
  
  // nextFree returns the next free object from the cached span if one is available.
  // Otherwise it refills the cache with a span with an available object and
  // returns that object along with a flag indicating that this was a heavy
  // weight allocation. If it is a heavy weight allocation the caller must
  // determine whether a new GC cycle needs to be started or if the GC is active
  // whether this goroutine needs to assist the GC.
  func (c *mcache) nextFree(sizeclass uint8) (v gclinkptr, s *mspan, shouldhelpgc bool) {
  	s = c.alloc[sizeclass]
  	shouldhelpgc = false
  	freeIndex := s.nextFreeIndex()
  	if freeIndex == s.nelems {
  		// The span is full.
  		if uintptr(s.allocCount) != s.nelems {
  			println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
  			throw("s.allocCount != s.nelems && freeIndex == s.nelems")
  		}
  		systemstack(func() {
  			c.refill(int32(sizeclass))
  		})
  		shouldhelpgc = true
  		s = c.alloc[sizeclass]
  
  		freeIndex = s.nextFreeIndex()
  	}
  
  	if freeIndex >= s.nelems {
  		throw("freeIndex is not valid")
  	}
  
  	v = gclinkptr(freeIndex*s.elemsize + s.base())
  	s.allocCount++
  	if uintptr(s.allocCount) > s.nelems {
  		println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
  		throw("s.allocCount > s.nelems")
  	}
  	return
  }
  
  // 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, needzero bool) unsafe.Pointer {
  	if gcphase == _GCmarktermination {
  		throw("mallocgc called with gcphase == _GCmarktermination")
  	}
  
  	if size == 0 {
  		return unsafe.Pointer(&zerobase)
  	}
  
  	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 x unsafe.Pointer
  	noscan := typ == nil || typ.kind&kindNoPointers != 0
  	if size <= maxSmallSize {
  		if noscan && 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 noscan (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 != 0 {
  				// The object fits into existing tiny block.
  				x = unsafe.Pointer(c.tiny + off)
  				c.tinyoffset = off + size
  				c.local_tinyallocs++
  				mp.mallocing = 0
  				releasem(mp)
  				return x
  			}
  			// Allocate a new maxTinySize block.
  			span := c.alloc[tinySizeClass]
  			v := nextFreeFast(span)
  			if v == 0 {
  				v, _, shouldhelpgc = c.nextFree(tinySizeClass)
  			}
  			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 == 0 {
  				c.tiny = uintptr(x)
  				c.tinyoffset = size
  			}
  			size = maxTinySize
  		} else {
  			var sizeclass uint8
  			if size <= smallSizeMax-8 {
  				sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]
  			} else {
  				sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]
  			}
  			size = uintptr(class_to_size[sizeclass])
  			span := c.alloc[sizeclass]
  			v := nextFreeFast(span)
  			if v == 0 {
  				v, span, shouldhelpgc = c.nextFree(sizeclass)
  			}
  			x = unsafe.Pointer(v)
  			if needzero && span.needzero != 0 {
  				memclrNoHeapPointers(unsafe.Pointer(v), size)
  			}
  		}
  	} else {
  		var s *mspan
  		shouldhelpgc = true
  		systemstack(func() {
  			s = largeAlloc(size, needzero)
  		})
  		s.freeindex = 1
  		s.allocCount = 1
  		x = unsafe.Pointer(s.base())
  		size = s.elemsize
  	}
  
  	var scanSize uintptr
  	if noscan {
  		heapBitsSetTypeNoScan(uintptr(x))
  	} 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 {
  				scanSize = dataSize - typ.size + typ.ptrdata
  			}
  		} else {
  			scanSize = typ.ptrdata
  		}
  		c.local_scan += scanSize
  	}
  
  	// 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()
  
  	// Allocate black during GC.
  	// 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 != _GCoff {
  		gcmarknewobject(uintptr(x), size, scanSize)
  	}
  
  	if raceenabled {
  		racemalloc(x, size)
  	}
  
  	if msanenabled {
  		msanmalloc(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 && gcShouldStart(false) {
  		gcStart(gcBackgroundMode, false)
  	}
  
  	return x
  }
  
  func largeAlloc(size uintptr, needzero bool) *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(npages, 0, true, needzero)
  	if s == nil {
  		throw("out of memory")
  	}
  	s.limit = s.base() + size
  	heapBitsForSpan(s.base()).initSpan(s)
  	return s
  }
  
  // implementation of new builtin
  // compiler (both frontend and SSA backend) knows the signature
  // of this function
  func newobject(typ *_type) unsafe.Pointer {
  	return mallocgc(typ.size, typ, true)
  }
  
  //go:linkname reflect_unsafe_New reflect.unsafe_New
  func reflect_unsafe_New(typ *_type) unsafe.Pointer {
  	return newobject(typ)
  }
  
  // newarray allocates an array of n elements of type typ.
  func newarray(typ *_type, n int) unsafe.Pointer {
  	if n < 0 || uintptr(n) > maxSliceCap(typ.size) {
  		panic(plainError("runtime: allocation size out of range"))
  	}
  	return mallocgc(typ.size*uintptr(n), typ, true)
  }
  
  //go:linkname reflect_unsafe_NewArray reflect.unsafe_NewArray
  func reflect_unsafe_NewArray(typ *_type, n int) unsafe.Pointer {
  	return newarray(typ, n)
  }
  
  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 {
  	if GOOS == "plan9" {
  		// Plan 9 doesn't support floating point in note handler.
  		if g := getg(); g == g.m.gsignal {
  			return nextSampleNoFP()
  		}
  	}
  
  	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 := fastrand()%(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
  }
  
  // nextSampleNoFP is similar to nextSample, but uses older,
  // simpler code to avoid floating point.
  func nextSampleNoFP() int32 {
  	// Set first allocation sample size.
  	rate := MemProfileRate
  	if rate > 0x3fffffff { // make 2*rate not overflow
  		rate = 0x3fffffff
  	}
  	if rate != 0 {
  		return int32(int(fastrand()) % (2 * rate))
  	}
  	return 0
  }
  
  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).
  // The returned memory will be zeroed.
  //
  // Consider marking persistentalloc'd types go:notinheap.
  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
  }
  

View as plain text