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
;
92 PageSize
= 1<<PageShift
,
93 PageMask
= PageSize
- 1,
95 typedef uintptr PageID
; // address >> PageShift
99 // Computed constant. The definition of MaxSmallSize and the
100 // algorithm in msize.c produce some number of different allocation
101 // size classes. NumSizeClasses is that number. It's needed here
102 // because there are static arrays of this length; when msize runs its
103 // size choosing algorithm it double-checks that NumSizeClasses agrees.
106 // Tunable constants.
107 MaxSmallSize
= 32<<10,
109 FixAllocChunk
= 128<<10, // Chunk size for FixAlloc
110 MaxMCacheListLen
= 256, // Maximum objects on MCacheList
111 MaxMCacheSize
= 2<<20, // Maximum bytes in one MCache
112 MaxMHeapList
= 1<<(20 - PageShift
), // Maximum page length for fixed-size list in MHeap.
113 HeapAllocChunk
= 1<<20, // Chunk size for heap growth
115 // Number of bits in page to span calculations (4k pages).
116 // On 64-bit, we limit the arena to 16G, so 22 bits suffices.
117 // On 32-bit, we don't bother limiting anything: 20 bits for 4G.
118 #if __SIZEOF_POINTER__ == 8
124 // Max number of threads to run garbage collection.
125 // 2, 3, and 4 are all plausible maximums depending
126 // on the hardware details of the machine. The garbage
127 // collector scales well to 4 cpus.
131 // A generic linked list of blocks. (Typically the block is bigger than sizeof(MLink).)
137 // SysAlloc obtains a large chunk of zeroed memory from the
138 // operating system, typically on the order of a hundred kilobytes
139 // or a megabyte. If the pointer argument is non-nil, the caller
140 // wants a mapping there or nowhere.
142 // SysUnused notifies the operating system that the contents
143 // of the memory region are no longer needed and can be reused
144 // for other purposes. The program reserves the right to start
145 // accessing those pages in the future.
147 // SysFree returns it unconditionally; this is only used if
148 // an out-of-memory error has been detected midway through
149 // an allocation. It is okay if SysFree is a no-op.
151 // SysReserve reserves address space without allocating memory.
152 // If the pointer passed to it is non-nil, the caller wants the
153 // reservation there, but SysReserve can still choose another
154 // location if that one is unavailable.
156 // SysMap maps previously reserved address space for use.
158 void* runtime_SysAlloc(uintptr nbytes
);
159 void runtime_SysFree(void *v
, uintptr nbytes
);
160 void runtime_SysUnused(void *v
, uintptr nbytes
);
161 void runtime_SysMap(void *v
, uintptr nbytes
);
162 void* runtime_SysReserve(void *v
, uintptr nbytes
);
164 // FixAlloc is a simple free-list allocator for fixed size objects.
165 // Malloc uses a FixAlloc wrapped around SysAlloc to manages its
166 // MCache and MSpan objects.
168 // Memory returned by FixAlloc_Alloc is not zeroed.
169 // The caller is responsible for locking around FixAlloc calls.
170 // Callers can keep state in the object but the first word is
171 // smashed by freeing and reallocating.
175 void *(*alloc
)(uintptr
);
176 void (*first
)(void *arg
, byte
*p
); // called first time p is returned
181 uintptr inuse
; // in-use bytes now
182 uintptr sys
; // bytes obtained from system
185 void runtime_FixAlloc_Init(FixAlloc
*f
, uintptr size
, void *(*alloc
)(uintptr
), void (*first
)(void*, byte
*), void *arg
);
186 void* runtime_FixAlloc_Alloc(FixAlloc
*f
);
187 void runtime_FixAlloc_Free(FixAlloc
*f
, void *p
);
191 // Shared with Go: if you edit this structure, also edit extern.go.
194 // General statistics.
195 uint64 alloc
; // bytes allocated and still in use
196 uint64 total_alloc
; // bytes allocated (even if freed)
197 uint64 sys
; // bytes obtained from system (should be sum of xxx_sys below, no locking, approximate)
198 uint64 nlookup
; // number of pointer lookups
199 uint64 nmalloc
; // number of mallocs
200 uint64 nfree
; // number of frees
202 // Statistics about malloc heap.
203 // protected by mheap.Lock
204 uint64 heap_alloc
; // bytes allocated and still in use
205 uint64 heap_sys
; // bytes obtained from system
206 uint64 heap_idle
; // bytes in idle spans
207 uint64 heap_inuse
; // bytes in non-idle spans
208 uint64 heap_released
; // bytes released to the OS
209 uint64 heap_objects
; // total number of allocated objects
211 // Statistics about allocation of low-level fixed-size structures.
212 // Protected by FixAlloc locks.
213 uint64 stacks_inuse
; // bootstrap stacks
215 uint64 mspan_inuse
; // MSpan structures
217 uint64 mcache_inuse
; // MCache structures
219 uint64 buckhash_sys
; // profiling bucket hash table
221 // Statistics about garbage collector.
222 // Protected by stopping the world during GC.
223 uint64 next_gc
; // next GC (in heap_alloc time)
224 uint64 last_gc
; // last GC (in absolute time)
225 uint64 pause_total_ns
;
226 uint64 pause_ns
[256];
231 // Statistics about allocation size classes.
236 } by_size
[NumSizeClasses
];
240 __asm__ ("runtime.VmemStats");
243 // Size classes. Computed and initialized by InitSizes.
245 // SizeToClass(0 <= n <= MaxSmallSize) returns the size class,
246 // 1 <= sizeclass < NumSizeClasses, for n.
247 // Size class 0 is reserved to mean "not small".
249 // class_to_size[i] = largest size in class i
250 // class_to_allocnpages[i] = number of pages to allocate when
251 // making new objects in class i
252 // class_to_transfercount[i] = number of objects to move when
253 // taking a bunch of objects out of the central lists
254 // and putting them in the thread free list.
256 int32
runtime_SizeToClass(int32
);
257 extern int32 runtime_class_to_size
[NumSizeClasses
];
258 extern int32 runtime_class_to_allocnpages
[NumSizeClasses
];
259 extern int32 runtime_class_to_transfercount
[NumSizeClasses
];
260 extern void runtime_InitSizes(void);
263 // Per-thread (in Go, per-M) cache for small objects.
264 // No locking needed because it is per-thread (per-M).
265 typedef struct MCacheList MCacheList
;
275 MCacheList list
[NumSizeClasses
];
277 int64 local_cachealloc
; // bytes allocated (or freed) from cache since last lock of heap
278 int64 local_objects
; // objects allocated (or freed) from cache since last lock of heap
279 int64 local_alloc
; // bytes allocated (or freed) since last lock of heap
280 int64 local_total_alloc
; // bytes allocated (even if freed) since last lock of heap
281 int64 local_nmalloc
; // number of mallocs since last lock of heap
282 int64 local_nfree
; // number of frees since last lock of heap
283 int64 local_nlookup
; // number of pointer lookups since last lock of heap
284 int32 next_sample
; // trigger heap sample after allocating this many bytes
285 // Statistics about allocation size classes since last lock of heap
289 } local_by_size
[NumSizeClasses
];
293 void* runtime_MCache_Alloc(MCache
*c
, int32 sizeclass
, uintptr size
, int32 zeroed
);
294 void runtime_MCache_Free(MCache
*c
, void *p
, int32 sizeclass
, uintptr size
);
295 void runtime_MCache_ReleaseAll(MCache
*c
);
297 // An MSpan is a run of pages.
307 MSpan
*next
; // in a span linked list
308 MSpan
*prev
; // in a span linked list
309 MSpan
*allnext
; // in the list of all spans
310 PageID start
; // starting page number
311 uintptr npages
; // number of pages in span
312 MLink
*freelist
; // list of free objects
313 uint32 ref
; // number of allocated objects in this span
314 uint32 sizeclass
; // size class
315 uint32 state
; // MSpanInUse etc
316 int64 unusedsince
; // First time spotted by GC in MSpanFree state
317 uintptr npreleased
; // number of pages released to the OS
318 byte
*limit
; // end of data in span
321 void runtime_MSpan_Init(MSpan
*span
, PageID start
, uintptr npages
);
323 // Every MSpan is in one doubly-linked list,
324 // either one of the MHeap's free lists or one of the
325 // MCentral's span lists. We use empty MSpan structures as list heads.
326 void runtime_MSpanList_Init(MSpan
*list
);
327 bool runtime_MSpanList_IsEmpty(MSpan
*list
);
328 void runtime_MSpanList_Insert(MSpan
*list
, MSpan
*span
);
329 void runtime_MSpanList_Remove(MSpan
*span
); // from whatever list it is in
332 // Central list of free objects of a given size.
342 void runtime_MCentral_Init(MCentral
*c
, int32 sizeclass
);
343 int32
runtime_MCentral_AllocList(MCentral
*c
, int32 n
, MLink
**first
);
344 void runtime_MCentral_FreeList(MCentral
*c
, int32 n
, MLink
*first
);
347 // The heap itself is the "free[]" and "large" arrays,
348 // but all the other global data is here too.
352 MSpan free
[MaxMHeapList
]; // free lists of given length
353 MSpan large
; // free lists length >= MaxMHeapList
357 MSpan
*map
[1<<MHeapMap_Bits
];
359 // range of addresses we might see in the heap
361 uintptr bitmap_mapped
;
366 // central free lists for small size classes.
367 // the union makes sure that the MCentrals are
368 // spaced CacheLineSize bytes apart, so that each MCentral.Lock
369 // gets its own cache line.
372 byte pad
[CacheLineSize
];
373 } central
[NumSizeClasses
];
375 FixAlloc spanalloc
; // allocator for Span*
376 FixAlloc cachealloc
; // allocator for MCache*
378 extern MHeap runtime_mheap
;
380 void runtime_MHeap_Init(MHeap
*h
, void *(*allocator
)(uintptr
));
381 MSpan
* runtime_MHeap_Alloc(MHeap
*h
, uintptr npage
, int32 sizeclass
, int32 acct
);
382 void runtime_MHeap_Free(MHeap
*h
, MSpan
*s
, int32 acct
);
383 MSpan
* runtime_MHeap_Lookup(MHeap
*h
, void *v
);
384 MSpan
* runtime_MHeap_LookupMaybe(MHeap
*h
, void *v
);
385 void runtime_MGetSizeClassInfo(int32 sizeclass
, uintptr
*size
, int32
*npages
, int32
*nobj
);
386 void* runtime_MHeap_SysAlloc(MHeap
*h
, uintptr n
);
387 void runtime_MHeap_MapBits(MHeap
*h
);
388 void runtime_MHeap_Scavenger(void*);
390 void* runtime_mallocgc(uintptr size
, uint32 flag
, int32 dogc
, int32 zeroed
);
391 int32
runtime_mlookup(void *v
, byte
**base
, uintptr
*size
, MSpan
**s
);
392 void runtime_gc(int32 force
);
393 void runtime_markallocated(void *v
, uintptr n
, bool noptr
);
394 void runtime_checkallocated(void *v
, uintptr n
);
395 void runtime_markfreed(void *v
, uintptr n
);
396 void runtime_checkfreed(void *v
, uintptr n
);
397 int32 runtime_checking
;
398 void runtime_markspan(void *v
, uintptr size
, uintptr n
, bool leftover
);
399 void runtime_unmarkspan(void *v
, uintptr size
);
400 bool runtime_blockspecial(void*);
401 void runtime_setblockspecial(void*, bool);
402 void runtime_purgecachedstats(M
*);
407 FlagNoPointers
= 1<<0, // no pointers here
408 FlagNoProfiling
= 1<<1, // must not profile
409 FlagNoGC
= 1<<2, // must not free or scan for pointers
412 void runtime_MProf_Malloc(void*, uintptr
);
413 void runtime_MProf_Free(void*, uintptr
);
414 void runtime_MProf_GC(void);
415 void runtime_MProf_Mark(void (*scan
)(byte
*, int64
));
416 int32
runtime_helpgc(bool*);
417 void runtime_gchelper(void);
419 struct __go_func_type
;
420 bool runtime_getfinalizer(void *p
, bool del
, void (**fn
)(void*), const struct __go_func_type
**ft
);
421 void runtime_walkfintab(void (*fn
)(void*), void (*scan
)(byte
*, int64
));