| // Copyright 2009 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 a 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 C code was written with an eye toward translating to Go |
| // in the future. Methods have the form Type_Method(Type *t, ...). |
| |
| typedef struct MCentral MCentral; |
| typedef struct MHeap MHeap; |
| typedef struct mspan MSpan; |
| typedef struct mstats MStats; |
| typedef struct mlink MLink; |
| typedef struct mtypes MTypes; |
| typedef struct gcstats GCStats; |
| |
| enum |
| { |
| PageShift = 13, |
| PageSize = 1<<PageShift, |
| PageMask = PageSize - 1, |
| }; |
| typedef uintptr PageID; // address >> PageShift |
| |
| enum |
| { |
| // Computed constant. The definition of MaxSmallSize and the |
| // algorithm in msize.c produce 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 is defined in runtime2.go as 67. |
| |
| // Tunable constants. |
| MaxSmallSize = 32<<10, |
| |
| // Tiny allocator parameters, see "Tiny allocator" comment in malloc.goc. |
| 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 |
| |
| // Number of bits in page to span calculations (4k pages). |
| // On Windows 64-bit we limit the arena to 32GB or 35 bits (see below for reason). |
| // On other 64-bit platforms, we limit the arena to 128GB, or 37 bits. |
| // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address. |
| #if __SIZEOF_POINTER__ == 8 |
| #ifdef GOOS_windows |
| // Windows counts memory used by page table into committed memory |
| // of the process, so we can't reserve too much memory. |
| // See http://golang.org/issue/5402 and http://golang.org/issue/5236. |
| MHeapMap_Bits = 35 - PageShift, |
| #else |
| MHeapMap_Bits = 37 - PageShift, |
| #endif |
| #else |
| MHeapMap_Bits = 32 - PageShift, |
| #endif |
| }; |
| |
| // Maximum memory allocation size, a hint for callers. |
| // This must be a #define instead of an enum because it |
| // is so large. |
| #if __SIZEOF_POINTER__ == 8 |
| #define MaxMem (1ULL<<(MHeapMap_Bits+PageShift)) /* 128 GB or 32 GB */ |
| #else |
| #define MaxMem ((uintptr)-1) |
| #endif |
| // 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. |
| |
| void* runtime_SysAlloc(uintptr nbytes, uint64 *stat) |
| __asm__ (GOSYM_PREFIX "runtime.sysAlloc"); |
| void runtime_SysFree(void *v, uintptr nbytes, uint64 *stat) |
| __asm__ (GOSYM_PREFIX "runtime.sysFree"); |
| void runtime_SysUnused(void *v, uintptr nbytes); |
| void runtime_SysUsed(void *v, uintptr nbytes); |
| void runtime_SysMap(void *v, uintptr nbytes, bool reserved, uint64 *stat); |
| void* runtime_SysReserve(void *v, uintptr nbytes, bool *reserved); |
| void runtime_SysFault(void *v, uintptr nbytes); |
| |
| // FixAlloc is a simple free-list allocator for fixed size objects. |
| // Malloc uses a FixAlloc wrapped around SysAlloc to manages its |
| // MCache and MSpan objects. |
| // |
| // Memory returned by FixAlloc_Alloc is not zeroed. |
| // The caller is responsible for locking around FixAlloc calls. |
| // Callers can keep state in the object but the first word is |
| // smashed by freeing and reallocating. |
| struct FixAlloc |
| { |
| uintptr size; |
| void (*first)(void *arg, byte *p); // called first time p is returned |
| void* arg; |
| MLink* list; |
| byte* chunk; |
| uint32 nchunk; |
| uintptr inuse; // in-use bytes now |
| uint64* stat; |
| }; |
| |
| void runtime_FixAlloc_Init(FixAlloc *f, uintptr size, void (*first)(void*, byte*), void *arg, uint64 *stat); |
| void* runtime_FixAlloc_Alloc(FixAlloc *f); |
| void runtime_FixAlloc_Free(FixAlloc *f, void *p); |
| |
| extern MStats *mstats(void) |
| __asm__ (GOSYM_PREFIX "runtime.getMstats"); |
| void runtime_updatememstats(GCStats *stats) |
| __asm__ (GOSYM_PREFIX "runtime.updatememstats"); |
| |
| // Size classes. Computed and initialized by InitSizes. |
| // |
| // SizeToClass(0 <= n <= MaxSmallSize) returns the size class, |
| // 1 <= sizeclass < _NumSizeClasses, for n. |
| // Size class 0 is reserved to mean "not small". |
| // |
| // class_to_size[i] = largest size in class i |
| // class_to_allocnpages[i] = number of pages to allocate when |
| // making new objects in class i |
| |
| int32 runtime_SizeToClass(int32); |
| uintptr runtime_roundupsize(uintptr) |
| __asm__(GOSYM_PREFIX "runtime.roundupsize"); |
| extern int32 runtime_class_to_size[_NumSizeClasses]; |
| extern int32 runtime_class_to_allocnpages[_NumSizeClasses]; |
| extern int8 runtime_size_to_class8[1024/8 + 1]; |
| extern int8 runtime_size_to_class128[(MaxSmallSize-1024)/128 + 1]; |
| extern void runtime_InitSizes(void); |
| |
| |
| typedef struct mcachelist MCacheList; |
| |
| MSpan* runtime_MCache_Refill(MCache *c, int32 sizeclass); |
| void runtime_MCache_Free(MCache *c, MLink *p, int32 sizeclass, uintptr size); |
| void runtime_MCache_ReleaseAll(MCache *c); |
| |
| // MTypes describes the types of blocks allocated within a span. |
| // The compression field describes the layout of the data. |
| // |
| // MTypes_Empty: |
| // All blocks are free, or no type information is available for |
| // allocated blocks. |
| // The data field has no meaning. |
| // MTypes_Single: |
| // The span contains just one block. |
| // The data field holds the type information. |
| // The sysalloc field has no meaning. |
| // MTypes_Words: |
| // The span contains multiple blocks. |
| // The data field points to an array of type [NumBlocks]uintptr, |
| // and each element of the array holds the type of the corresponding |
| // block. |
| // MTypes_Bytes: |
| // The span contains at most seven different types of blocks. |
| // The data field points to the following structure: |
| // struct { |
| // type [8]uintptr // type[0] is always 0 |
| // index [NumBlocks]byte |
| // } |
| // The type of the i-th block is: data.type[data.index[i]] |
| enum |
| { |
| MTypes_Empty = 0, |
| MTypes_Single = 1, |
| MTypes_Words = 2, |
| MTypes_Bytes = 3, |
| }; |
| |
| enum |
| { |
| KindSpecialFinalizer = 1, |
| KindSpecialProfile = 2, |
| // Note: The finalizer special must be first because if we're freeing |
| // an object, a finalizer special will cause the freeing operation |
| // to abort, and we want to keep the other special records around |
| // if that happens. |
| }; |
| |
| typedef struct special Special; |
| |
| // The described object has a finalizer set for it. |
| typedef struct SpecialFinalizer SpecialFinalizer; |
| struct SpecialFinalizer |
| { |
| Special; |
| FuncVal* fn; |
| const FuncType* ft; |
| const PtrType* ot; |
| }; |
| |
| // The described object is being heap profiled. |
| typedef struct bucket Bucket; // from mprof.go |
| typedef struct SpecialProfile SpecialProfile; |
| struct SpecialProfile |
| { |
| Special; |
| Bucket* b; |
| }; |
| |
| // An MSpan is a run of pages. |
| enum |
| { |
| MSpanInUse = 0, |
| MSpanFree, |
| MSpanListHead, |
| MSpanDead, |
| }; |
| |
| void runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages); |
| void runtime_MSpan_EnsureSwept(MSpan *span); |
| bool runtime_MSpan_Sweep(MSpan *span); |
| |
| // Every MSpan is in one doubly-linked list, |
| // either one of the MHeap's free lists or one of the |
| // MCentral's span lists. We use empty MSpan structures as list heads. |
| void runtime_MSpanList_Init(MSpan *list); |
| bool runtime_MSpanList_IsEmpty(MSpan *list); |
| void runtime_MSpanList_Insert(MSpan *list, MSpan *span); |
| void runtime_MSpanList_InsertBack(MSpan *list, MSpan *span); |
| void runtime_MSpanList_Remove(MSpan *span); // from whatever list it is in |
| |
| |
| // Central list of free objects of a given size. |
| struct MCentral |
| { |
| Lock; |
| int32 sizeclass; |
| MSpan nonempty; // list of spans with a free object |
| MSpan mempty; // list of spans with no free objects (or cached in an MCache) |
| int32 nfree; // # of objects available in nonempty spans |
| }; |
| |
| void runtime_MCentral_Init(MCentral *c, int32 sizeclass); |
| MSpan* runtime_MCentral_CacheSpan(MCentral *c); |
| void runtime_MCentral_UncacheSpan(MCentral *c, MSpan *s); |
| bool runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end); |
| void runtime_MCentral_FreeList(MCentral *c, MLink *start); // TODO: need this? |
| |
| // Main malloc heap. |
| // The heap itself is the "free[]" and "large" arrays, |
| // but all the other global data is here too. |
| struct MHeap |
| { |
| Lock; |
| MSpan free[MaxMHeapList]; // free lists of given length |
| MSpan freelarge; // free lists length >= MaxMHeapList |
| MSpan busy[MaxMHeapList]; // busy lists of large objects of given length |
| MSpan busylarge; // busy lists of large objects length >= MaxMHeapList |
| MSpan **allspans; // all spans out there |
| MSpan **sweepspans; // copy of allspans referenced by sweeper |
| uint32 nspan; |
| uint32 nspancap; |
| uint32 sweepgen; // sweep generation, see comment in MSpan |
| uint32 sweepdone; // all spans are swept |
| |
| // span lookup |
| MSpan** spans; |
| uintptr spans_mapped; |
| |
| // range of addresses we might see in the heap |
| byte *bitmap; |
| uintptr bitmap_mapped; |
| byte *arena_start; |
| byte *arena_used; |
| byte *arena_end; |
| bool arena_reserved; |
| |
| // central free lists for small size classes. |
| // the padding makes sure that the MCentrals are |
| // spaced CacheLineSize bytes apart, so that each MCentral.Lock |
| // gets its own cache line. |
| struct { |
| MCentral; |
| byte pad[64]; |
| } central[_NumSizeClasses]; |
| |
| FixAlloc spanalloc; // allocator for Span* |
| FixAlloc cachealloc; // allocator for MCache* |
| FixAlloc specialfinalizeralloc; // allocator for SpecialFinalizer* |
| FixAlloc specialprofilealloc; // allocator for SpecialProfile* |
| Lock speciallock; // lock for sepcial record allocators. |
| |
| // Malloc stats. |
| uint64 largefree; // bytes freed for large objects (>MaxSmallSize) |
| uint64 nlargefree; // number of frees for large objects (>MaxSmallSize) |
| uint64 nsmallfree[_NumSizeClasses]; // number of frees for small objects (<=MaxSmallSize) |
| }; |
| extern MHeap runtime_mheap; |
| |
| void runtime_MHeap_Init(MHeap *h); |
| MSpan* runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, bool large, bool needzero); |
| void runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct); |
| MSpan* runtime_MHeap_Lookup(MHeap *h, void *v); |
| MSpan* runtime_MHeap_LookupMaybe(MHeap *h, void *v); |
| void runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *size, int32 *npages, int32 *nobj); |
| void* runtime_MHeap_SysAlloc(MHeap *h, uintptr n); |
| void runtime_MHeap_MapBits(MHeap *h); |
| void runtime_MHeap_MapSpans(MHeap *h); |
| void runtime_MHeap_SplitSpan(MHeap *h, MSpan *s); |
| |
| void* runtime_mallocgc(uintptr size, uintptr typ, uint32 flag); |
| void* runtime_persistentalloc(uintptr size, uintptr align, uint64 *stat) |
| __asm__(GOSYM_PREFIX "runtime.persistentalloc"); |
| int32 runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **s); |
| void runtime_gc(int32 force) |
| __asm__(GOSYM_PREFIX "runtime.gc"); |
| uintptr runtime_sweepone(void); |
| void runtime_markscan(void *v); |
| void runtime_marknogc(void *v); |
| void runtime_checkallocated(void *v, uintptr n); |
| void runtime_markfreed(void *v); |
| void runtime_checkfreed(void *v, uintptr n); |
| extern int32 runtime_checking; |
| void runtime_markspan(void *v, uintptr size, uintptr n, bool leftover); |
| void runtime_unmarkspan(void *v, uintptr size); |
| void runtime_purgecachedstats(MCache*); |
| void* runtime_cnew(const Type*) |
| __asm__(GOSYM_PREFIX "runtime.newobject"); |
| void* runtime_cnewarray(const Type*, intgo) |
| __asm__(GOSYM_PREFIX "runtime.newarray"); |
| void runtime_tracealloc(void*, uintptr, uintptr) |
| __asm__ (GOSYM_PREFIX "runtime.tracealloc"); |
| void runtime_tracefree(void*, uintptr) |
| __asm__ (GOSYM_PREFIX "runtime.tracefree"); |
| void runtime_tracegc(void) |
| __asm__ (GOSYM_PREFIX "runtime.tracegc"); |
| |
| uintptr runtime_gettype(void*); |
| |
| enum |
| { |
| // flags to malloc |
| FlagNoScan = 1<<0, // GC doesn't have to scan object |
| FlagNoProfiling = 1<<1, // must not profile |
| FlagNoGC = 1<<2, // must not free or scan for pointers |
| FlagNoZero = 1<<3, // don't zero memory |
| FlagNoInvokeGC = 1<<4, // don't invoke GC |
| }; |
| |
| typedef struct Obj Obj; |
| struct Obj |
| { |
| byte *p; // data pointer |
| uintptr n; // size of data in bytes |
| uintptr ti; // type info |
| }; |
| |
| void runtime_MProf_Malloc(void*, uintptr) |
| __asm__ (GOSYM_PREFIX "runtime.mProf_Malloc"); |
| void runtime_MProf_Free(Bucket*, uintptr, bool) |
| __asm__ (GOSYM_PREFIX "runtime.mProf_Free"); |
| void runtime_MProf_GC(void) |
| __asm__ (GOSYM_PREFIX "runtime.mProf_GC"); |
| void runtime_iterate_memprof(FuncVal* callback) |
| __asm__ (GOSYM_PREFIX "runtime.iterate_memprof"); |
| int32 runtime_gcprocs(void) |
| __asm__ (GOSYM_PREFIX "runtime.gcprocs"); |
| void runtime_helpgc(int32 nproc) |
| __asm__ (GOSYM_PREFIX "runtime.helpgc"); |
| void runtime_gchelper(void) |
| __asm__ (GOSYM_PREFIX "runtime.gchelper"); |
| |
| void runtime_setprofilebucket(void *p, Bucket *b) |
| __asm__ (GOSYM_PREFIX "runtime.setprofilebucket"); |
| |
| struct __go_func_type; |
| struct __go_ptr_type; |
| bool runtime_addfinalizer(void *p, FuncVal *fn, const struct __go_func_type*, const struct __go_ptr_type*) |
| __asm__ (GOSYM_PREFIX "runtime.addfinalizer"); |
| void runtime_removefinalizer(void*) |
| __asm__ (GOSYM_PREFIX "runtime.removefinalizer"); |
| void runtime_queuefinalizer(void *p, FuncVal *fn, const struct __go_func_type *ft, const struct __go_ptr_type *ot) |
| __asm__ (GOSYM_PREFIX "runtime.queuefinalizer"); |
| |
| void runtime_freeallspecials(MSpan *span, void *p, uintptr size); |
| bool runtime_freespecial(Special *s, void *p, uintptr size, bool freed); |
| |
| enum |
| { |
| TypeInfo_SingleObject = 0, |
| TypeInfo_Array = 1, |
| TypeInfo_Chan = 2, |
| |
| // Enables type information at the end of blocks allocated from heap |
| DebugTypeAtBlockEnd = 0, |
| }; |
| |
| // Information from the compiler about the layout of stack frames. |
| typedef struct BitVector BitVector; |
| struct BitVector |
| { |
| int32 n; // # of bits |
| uint32 *data; |
| }; |
| typedef struct StackMap StackMap; |
| struct StackMap |
| { |
| int32 n; // number of bitmaps |
| int32 nbit; // number of bits in each bitmap |
| uint32 data[]; |
| }; |
| enum { |
| // Pointer map |
| BitsPerPointer = 2, |
| BitsDead = 0, |
| BitsScalar = 1, |
| BitsPointer = 2, |
| BitsMultiWord = 3, |
| // BitsMultiWord will be set for the first word of a multi-word item. |
| // When it is set, one of the following will be set for the second word. |
| BitsString = 0, |
| BitsSlice = 1, |
| BitsIface = 2, |
| BitsEface = 3, |
| }; |
| // Returns pointer map data for the given stackmap index |
| // (the index is encoded in PCDATA_StackMapIndex). |
| BitVector runtime_stackmapdata(StackMap *stackmap, int32 n); |
| |
| // defined in mgc0.go |
| void runtime_gc_m_ptr(Eface*); |
| void runtime_gc_g_ptr(Eface*); |
| void runtime_gc_itab_ptr(Eface*); |
| |
| void runtime_memorydump(void); |
| int32 runtime_setgcpercent(int32) |
| __asm__ (GOSYM_PREFIX "runtime.setgcpercent"); |
| |
| // Value we use to mark dead pointers when GODEBUG=gcdead=1. |
| #define PoisonGC ((uintptr)0xf969696969696969ULL) |
| #define PoisonStack ((uintptr)0x6868686868686868ULL) |
| |
| struct Workbuf; |