1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Memory allocator, based on tcmalloc.
6 // http://goog-perftools.sourceforge.net/doc/tcmalloc.html
8 // The main allocator works in runs of pages.
9 // Small allocation sizes (up to and including 32 kB) are
10 // rounded to one of about 100 size classes, each of which
11 // has its own free list of objects of exactly that size.
12 // Any free page of memory can be split into a set of objects
13 // of one size class, which are then managed using free list
16 // The allocator's data structures are:
18 // FixAlloc: a free-list allocator for fixed-size objects,
19 // used to manage storage used by the allocator.
20 // MHeap: the malloc heap, managed at page (4096-byte) granularity.
21 // MSpan: a run of pages managed by the MHeap.
22 // MCentral: a shared free list for a given size class.
23 // MCache: a per-thread (in Go, per-M) cache for small objects.
24 // MStats: allocation statistics.
26 // Allocating a small object proceeds up a hierarchy of caches:
28 // 1. Round the size up to one of the small size classes
29 // and look in the corresponding MCache free list.
30 // If the list is not empty, allocate an object from it.
31 // This can all be done without acquiring a lock.
33 // 2. If the MCache free list is empty, replenish it by
34 // taking a bunch of objects from the MCentral free list.
35 // Moving a bunch amortizes the cost of acquiring the MCentral lock.
37 // 3. If the MCentral free list is empty, replenish it by
38 // allocating a run of pages from the MHeap and then
39 // chopping that memory into a objects of the given size.
40 // Allocating many objects amortizes the cost of locking
43 // 4. If the MHeap is empty or has no page runs large enough,
44 // allocate a new group of pages (at least 1MB) from the
45 // operating system. Allocating a large run of pages
46 // amortizes the cost of talking to the operating system.
48 // Freeing a small object proceeds up the same hierarchy:
50 // 1. Look up the size class for the object and add it to
51 // the MCache free list.
53 // 2. If the MCache free list is too long or the MCache has
54 // too much memory, return some to the MCentral free lists.
56 // 3. If all the objects in a given span have returned to
57 // the MCentral list, return that span to the page heap.
59 // 4. If the heap has too much memory, return some to the
62 // TODO(rsc): Step 4 is not implemented.
64 // Allocating and freeing a large object uses the page heap
65 // directly, bypassing the MCache and MCentral free lists.
67 // The small objects on the MCache and MCentral free lists
68 // may or may not be zeroed. They are zeroed if and only if
69 // the second word of the object is zero. The spans in the
70 // page heap are always zeroed. When a span full of objects
71 // is returned to the page heap, the objects that need to be
72 // are zeroed first. There are two main benefits to delaying the
75 // 1. stack frames allocated from the small object lists
76 // can avoid zeroing altogether.
77 // 2. the cost of zeroing when reusing a small object is
78 // charged to the mutator, not the garbage collector.
80 // This C code was written with an eye toward translating to Go
81 // in the future. Methods have the form Type_Method(Type *t, ...).
83 typedef struct MCentral MCentral;
84 typedef struct MHeap MHeap;
85 typedef struct MSpan MSpan;
86 typedef struct MStats MStats;
87 typedef struct MLink MLink;
88 typedef struct MTypes MTypes;
89 typedef struct GCStats GCStats;
94 PageSize = 1<<PageShift,
95 PageMask = PageSize - 1,
97 typedef uintptr PageID; // address >> PageShift
101 // Computed constant. The definition of MaxSmallSize and the
102 // algorithm in msize.c produce some number of different allocation
103 // size classes. NumSizeClasses is that number. It's needed here
104 // because there are static arrays of this length; when msize runs its
105 // size choosing algorithm it double-checks that NumSizeClasses agrees.
108 // Tunable constants.
109 MaxSmallSize = 32<<10,
111 FixAllocChunk = 128<<10, // Chunk size for FixAlloc
112 MaxMCacheListLen = 256, // Maximum objects on MCacheList
113 MaxMCacheSize = 2<<20, // Maximum bytes in one MCache
114 MaxMHeapList = 1<<(20 - PageShift), // Maximum page length for fixed-size list in MHeap.
115 HeapAllocChunk = 1<<20, // Chunk size for heap growth
117 // Number of bits in page to span calculations (4k pages).
118 // On Windows 64-bit we limit the arena to 32GB or 35 bits (see below for reason).
119 // On other 64-bit platforms, we limit the arena to 128GB, or 37 bits.
120 // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address.
121 #if __SIZEOF_POINTER__ == 8
123 // Windows counts memory used by page table into committed memory
124 // of the process, so we can't reserve too much memory.
125 // See http://golang.org/issue/5402 and http://golang.org/issue/5236.
126 MHeapMap_Bits = 35 - PageShift,
128 MHeapMap_Bits = 37 - PageShift,
131 MHeapMap_Bits = 32 - PageShift,
134 // Max number of threads to run garbage collection.
135 // 2, 3, and 4 are all plausible maximums depending
136 // on the hardware details of the machine. The garbage
137 // collector scales well to 8 cpus.
141 // Maximum memory allocation size, a hint for callers.
142 // This must be a #define instead of an enum because it
144 #if __SIZEOF_POINTER__ == 8
145 #define MaxMem (1ULL<<(MHeapMap_Bits+PageShift)) /* 128 GB or 32 GB */
147 #define MaxMem ((uintptr)-1)
150 // A generic linked list of blocks. (Typically the block is bigger than sizeof(MLink).)
156 // SysAlloc obtains a large chunk of zeroed memory from the
157 // operating system, typically on the order of a hundred kilobytes
158 // or a megabyte. If the pointer argument is non-nil, the caller
159 // wants a mapping there or nowhere.
161 // SysUnused notifies the operating system that the contents
162 // of the memory region are no longer needed and can be reused
163 // for other purposes. The program reserves the right to start
164 // accessing those pages in the future.
166 // SysFree returns it unconditionally; this is only used if
167 // an out-of-memory error has been detected midway through
168 // an allocation. It is okay if SysFree is a no-op.
170 // SysReserve reserves address space without allocating memory.
171 // If the pointer passed to it is non-nil, the caller wants the
172 // reservation there, but SysReserve can still choose another
173 // location if that one is unavailable.
175 // SysMap maps previously reserved address space for use.
177 void* runtime_SysAlloc(uintptr nbytes);
178 void runtime_SysFree(void *v, uintptr nbytes);
179 void runtime_SysUnused(void *v, uintptr nbytes);
180 void runtime_SysMap(void *v, uintptr nbytes);
181 void* runtime_SysReserve(void *v, uintptr nbytes);
183 // FixAlloc is a simple free-list allocator for fixed size objects.
184 // Malloc uses a FixAlloc wrapped around SysAlloc to manages its
185 // MCache and MSpan objects.
187 // Memory returned by FixAlloc_Alloc is not zeroed.
188 // The caller is responsible for locking around FixAlloc calls.
189 // Callers can keep state in the object but the first word is
190 // smashed by freeing and reallocating.
194 void *(*alloc)(uintptr);
195 void (*first)(void *arg, byte *p); // called first time p is returned
200 uintptr inuse; // in-use bytes now
201 uintptr sys; // bytes obtained from system
204 void runtime_FixAlloc_Init(FixAlloc *f, uintptr size, void *(*alloc)(uintptr), void (*first)(void*, byte*), void *arg);
205 void* runtime_FixAlloc_Alloc(FixAlloc *f);
206 void runtime_FixAlloc_Free(FixAlloc *f, void *p);
210 // Shared with Go: if you edit this structure, also edit type MemStats in mem.go.
213 // General statistics.
214 uint64 alloc; // bytes allocated and still in use
215 uint64 total_alloc; // bytes allocated (even if freed)
216 uint64 sys; // bytes obtained from system (should be sum of xxx_sys below, no locking, approximate)
217 uint64 nlookup; // number of pointer lookups
218 uint64 nmalloc; // number of mallocs
219 uint64 nfree; // number of frees
221 // Statistics about malloc heap.
222 // protected by mheap.Lock
223 uint64 heap_alloc; // bytes allocated and still in use
224 uint64 heap_sys; // bytes obtained from system
225 uint64 heap_idle; // bytes in idle spans
226 uint64 heap_inuse; // bytes in non-idle spans
227 uint64 heap_released; // bytes released to the OS
228 uint64 heap_objects; // total number of allocated objects
230 // Statistics about allocation of low-level fixed-size structures.
231 // Protected by FixAlloc locks.
232 uint64 stacks_inuse; // bootstrap stacks
234 uint64 mspan_inuse; // MSpan structures
236 uint64 mcache_inuse; // MCache structures
238 uint64 buckhash_sys; // profiling bucket hash table
240 // Statistics about garbage collector.
241 // Protected by mheap or stopping the world during GC.
242 uint64 next_gc; // next GC (in heap_alloc time)
243 uint64 last_gc; // last GC (in absolute time)
244 uint64 pause_total_ns;
245 uint64 pause_ns[256];
250 // Statistics about allocation size classes.
255 } by_size[NumSizeClasses];
259 __asm__ (GOSYM_PREFIX "runtime.VmemStats");
261 // Size classes. Computed and initialized by InitSizes.
263 // SizeToClass(0 <= n <= MaxSmallSize) returns the size class,
264 // 1 <= sizeclass < NumSizeClasses, for n.
265 // Size class 0 is reserved to mean "not small".
267 // class_to_size[i] = largest size in class i
268 // class_to_allocnpages[i] = number of pages to allocate when
269 // making new objects in class i
270 // class_to_transfercount[i] = number of objects to move when
271 // taking a bunch of objects out of the central lists
272 // and putting them in the thread free list.
274 int32 runtime_SizeToClass(int32);
275 extern int32 runtime_class_to_size[NumSizeClasses];
276 extern int32 runtime_class_to_allocnpages[NumSizeClasses];
277 extern int32 runtime_class_to_transfercount[NumSizeClasses];
278 extern void runtime_InitSizes(void);
281 // Per-thread (in Go, per-M) cache for small objects.
282 // No locking needed because it is per-thread (per-M).
283 typedef struct MCacheList MCacheList;
293 MCacheList list[NumSizeClasses];
295 intptr local_cachealloc; // bytes allocated (or freed) from cache since last lock of heap
296 intptr local_objects; // objects allocated (or freed) from cache since last lock of heap
297 intptr local_alloc; // bytes allocated (or freed) since last lock of heap
298 uintptr local_total_alloc; // bytes allocated (even if freed) since last lock of heap
299 uintptr local_nmalloc; // number of mallocs since last lock of heap
300 uintptr local_nfree; // number of frees since last lock of heap
301 uintptr local_nlookup; // number of pointer lookups since last lock of heap
302 int32 next_sample; // trigger heap sample after allocating this many bytes
303 // Statistics about allocation size classes since last lock of heap
307 } local_by_size[NumSizeClasses];
311 void* runtime_MCache_Alloc(MCache *c, int32 sizeclass, uintptr size, int32 zeroed);
312 void runtime_MCache_Free(MCache *c, void *p, int32 sizeclass, uintptr size);
313 void runtime_MCache_ReleaseAll(MCache *c);
315 // MTypes describes the types of blocks allocated within a span.
316 // The compression field describes the layout of the data.
319 // All blocks are free, or no type information is available for
321 // The data field has no meaning.
323 // The span contains just one block.
324 // The data field holds the type information.
325 // The sysalloc field has no meaning.
327 // The span contains multiple blocks.
328 // The data field points to an array of type [NumBlocks]uintptr,
329 // and each element of the array holds the type of the corresponding
332 // The span contains at most seven different types of blocks.
333 // The data field points to the following structure:
335 // type [8]uintptr // type[0] is always 0
336 // index [NumBlocks]byte
338 // The type of the i-th block is: data.type[data.index[i]]
348 byte compression; // one of MTypes_*
349 bool sysalloc; // whether (void*)data is from runtime_SysAlloc
353 // An MSpan is a run of pages.
363 MSpan *next; // in a span linked list
364 MSpan *prev; // in a span linked list
365 PageID start; // starting page number
366 uintptr npages; // number of pages in span
367 MLink *freelist; // list of free objects
368 uint32 ref; // number of allocated objects in this span
369 int32 sizeclass; // size class
370 uintptr elemsize; // computed from sizeclass or from npages
371 uint32 state; // MSpanInUse etc
372 int64 unusedsince; // First time spotted by GC in MSpanFree state
373 uintptr npreleased; // number of pages released to the OS
374 byte *limit; // end of data in span
375 MTypes types; // types of allocated objects in this span
378 void runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages);
380 // Every MSpan is in one doubly-linked list,
381 // either one of the MHeap's free lists or one of the
382 // MCentral's span lists. We use empty MSpan structures as list heads.
383 void runtime_MSpanList_Init(MSpan *list);
384 bool runtime_MSpanList_IsEmpty(MSpan *list);
385 void runtime_MSpanList_Insert(MSpan *list, MSpan *span);
386 void runtime_MSpanList_Remove(MSpan *span); // from whatever list it is in
389 // Central list of free objects of a given size.
399 void runtime_MCentral_Init(MCentral *c, int32 sizeclass);
400 int32 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **first);
401 void runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *first);
402 void runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end);
405 // The heap itself is the "free[]" and "large" arrays,
406 // but all the other global data is here too.
410 MSpan free[MaxMHeapList]; // free lists of given length
411 MSpan large; // free lists length >= MaxMHeapList
417 MSpan *map[1<<MHeapMap_Bits];
419 // range of addresses we might see in the heap
421 uintptr bitmap_mapped;
426 // central free lists for small size classes.
427 // the padding makes sure that the MCentrals are
428 // spaced CacheLineSize bytes apart, so that each MCentral.Lock
429 // gets its own cache line.
433 } central[NumSizeClasses];
435 FixAlloc spanalloc; // allocator for Span*
436 FixAlloc cachealloc; // allocator for MCache*
438 extern MHeap *runtime_mheap;
440 void runtime_MHeap_Init(MHeap *h, void *(*allocator)(uintptr));
441 MSpan* runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct, int32 zeroed);
442 void runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct);
443 MSpan* runtime_MHeap_Lookup(MHeap *h, void *v);
444 MSpan* runtime_MHeap_LookupMaybe(MHeap *h, void *v);
445 void runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *size, int32 *npages, int32 *nobj);
446 void* runtime_MHeap_SysAlloc(MHeap *h, uintptr n);
447 void runtime_MHeap_MapBits(MHeap *h);
448 void runtime_MHeap_Scavenger(void*);
450 void* runtime_mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed);
451 int32 runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **s);
452 void runtime_gc(int32 force);
453 void runtime_markallocated(void *v, uintptr n, bool noptr);
454 void runtime_checkallocated(void *v, uintptr n);
455 void runtime_markfreed(void *v, uintptr n);
456 void runtime_checkfreed(void *v, uintptr n);
457 extern int32 runtime_checking;
458 void runtime_markspan(void *v, uintptr size, uintptr n, bool leftover);
459 void runtime_unmarkspan(void *v, uintptr size);
460 bool runtime_blockspecial(void*);
461 void runtime_setblockspecial(void*, bool);
462 void runtime_purgecachedstats(MCache*);
463 void* runtime_cnew(const Type*);
464 void* runtime_cnewarray(const Type*, intgo);
466 void runtime_settype(void*, uintptr);
467 void runtime_settype_flush(M*, bool);
468 void runtime_settype_sysfree(MSpan*);
469 uintptr runtime_gettype(void*);
474 FlagNoPointers = 1<<0, // no pointers here
475 FlagNoProfiling = 1<<1, // must not profile
476 FlagNoGC = 1<<2, // must not free or scan for pointers
479 typedef struct Obj Obj;
482 byte *p; // data pointer
483 uintptr n; // size of data in bytes
484 uintptr ti; // type info
487 void runtime_MProf_Malloc(void*, uintptr);
488 void runtime_MProf_Free(void*, uintptr);
489 void runtime_MProf_GC(void);
490 void runtime_MProf_Mark(void (*addroot)(Obj));
491 int32 runtime_gcprocs(void);
492 void runtime_helpgc(int32 nproc);
493 void runtime_gchelper(void);
495 struct __go_func_type;
496 bool runtime_getfinalizer(void *p, bool del, FuncVal **fn, const struct __go_func_type **ft);
497 void runtime_walkfintab(void (*fn)(void*), void (*scan)(Obj));
501 TypeInfo_SingleObject = 0,
506 // Enables type information at the end of blocks allocated from heap
507 DebugTypeAtBlockEnd = 0,
510 // defined in mgc0.go
511 void runtime_gc_m_ptr(Eface*);
512 void runtime_gc_itab_ptr(Eface*);
514 void runtime_memorydump(void);
516 void runtime_proc_scan(void (*)(Obj));
517 void runtime_time_scan(void (*)(Obj));