1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
|
// 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-M) 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. The spans in the
// page heap are always zeroed. When a span full of objects
// is returned to the page heap, the objects that need to be
// are zeroed first. There are two main benefits to delaying the
// zeroing this way:
//
// 1. stack frames allocated from the small object lists
// 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;
enum
{
PageShift = 12,
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 = 61,
// Tunable constants.
MaxSmallSize = 32<<10,
FixAllocChunk = 128<<10, // Chunk size for FixAlloc
MaxMCacheListLen = 256, // Maximum objects on MCacheList
MaxMCacheSize = 2<<20, // Maximum bytes in one MCache
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 64-bit, we limit the arena to 16G, so 22 bits suffices.
// On 32-bit, we don't bother limiting anything: 20 bits for 4G.
#if __SIZEOF_POINTER__ == 8
MHeapMap_Bits = 22,
#else
MHeapMap_Bits = 20,
#endif
};
// A generic linked list of blocks. (Typically the block is bigger than sizeof(MLink).)
struct MLink
{
MLink *next;
};
// SysAlloc obtains a large chunk of zeroed memory from the
// operating system, typically on the order of a hundred kilobytes
// or a megabyte. If the pointer argument is non-nil, the caller
// wants a mapping there or nowhere.
//
// SysUnused notifies the operating system that the contents
// of the memory region are no longer needed and can be reused
// for other purposes. The program reserves the right to start
// accessing those pages in the future.
//
// 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.
//
// SysMap maps previously reserved address space for use.
void* runtime_SysAlloc(uintptr nbytes);
void runtime_SysFree(void *v, uintptr nbytes);
void runtime_SysUnused(void *v, uintptr nbytes);
void runtime_SysMap(void *v, uintptr nbytes);
void* runtime_SysReserve(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 *(*alloc)(uintptr);
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
uintptr sys; // bytes obtained from system
};
void runtime_FixAlloc_Init(FixAlloc *f, uintptr size, void *(*alloc)(uintptr), void (*first)(void*, byte*), void *arg);
void* runtime_FixAlloc_Alloc(FixAlloc *f);
void runtime_FixAlloc_Free(FixAlloc *f, void *p);
// Statistics.
// Shared with Go: if you edit this structure, also edit extern.go.
struct MStats
{
// General statistics.
uint64 alloc; // bytes allocated and still in use
uint64 total_alloc; // bytes allocated (even if freed)
uint64 sys; // bytes obtained from system (should be sum of xxx_sys below, no locking, approximate)
uint64 nlookup; // number of pointer lookups
uint64 nmalloc; // number of mallocs
uint64 nfree; // number of frees
// Statistics about malloc heap.
// protected by mheap.Lock
uint64 heap_alloc; // bytes allocated and still in use
uint64 heap_sys; // bytes obtained from system
uint64 heap_idle; // bytes in idle spans
uint64 heap_inuse; // bytes in non-idle spans
uint64 heap_objects; // total number of allocated objects
// Statistics about allocation of low-level fixed-size structures.
// Protected by FixAlloc locks.
uint64 stacks_inuse; // bootstrap stacks
uint64 stacks_sys;
uint64 mspan_inuse; // MSpan structures
uint64 mspan_sys;
uint64 mcache_inuse; // MCache structures
uint64 mcache_sys;
uint64 buckhash_sys; // profiling bucket hash table
// Statistics about garbage collector.
// Protected by stopping the world during GC.
uint64 next_gc; // next GC (in heap_alloc time)
uint64 pause_total_ns;
uint64 pause_ns[256];
uint32 numgc;
bool enablegc;
bool debuggc;
// Statistics about allocation size classes.
struct {
uint32 size;
uint64 nmalloc;
uint64 nfree;
} by_size[NumSizeClasses];
};
extern MStats mstats
__asm__ ("libgo_runtime.runtime.MemStats");
// 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
// class_to_transfercount[i] = number of objects to move when
// taking a bunch of objects out of the central lists
// and putting them in the thread free list.
int32 runtime_SizeToClass(int32);
extern int32 runtime_class_to_size[NumSizeClasses];
extern int32 runtime_class_to_allocnpages[NumSizeClasses];
extern int32 runtime_class_to_transfercount[NumSizeClasses];
extern void runtime_InitSizes(void);
// Per-thread (in Go, per-M) cache for small objects.
// No locking needed because it is per-thread (per-M).
typedef struct MCacheList MCacheList;
struct MCacheList
{
MLink *list;
uint32 nlist;
uint32 nlistmin;
};
struct MCache
{
MCacheList list[NumSizeClasses];
uint64 size;
int64 local_cachealloc; // bytes allocated (or freed) from cache since last lock of heap
int64 local_objects; // objects allocated (or freed) from cache since last lock of heap
int64 local_alloc; // bytes allocated (or freed) since last lock of heap
int64 local_total_alloc; // bytes allocated (even if freed) since last lock of heap
int64 local_nmalloc; // number of mallocs since last lock of heap
int64 local_nfree; // number of frees since last lock of heap
int64 local_nlookup; // number of pointer lookups since last lock of heap
int32 next_sample; // trigger heap sample after allocating this many bytes
// Statistics about allocation size classes since last lock of heap
struct {
int64 nmalloc;
int64 nfree;
} local_by_size[NumSizeClasses];
};
void* runtime_MCache_Alloc(MCache *c, int32 sizeclass, uintptr size, int32 zeroed);
void runtime_MCache_Free(MCache *c, void *p, int32 sizeclass, uintptr size);
void runtime_MCache_ReleaseAll(MCache *c);
// An MSpan is a run of pages.
enum
{
MSpanInUse = 0,
MSpanFree,
MSpanListHead,
MSpanDead,
};
struct MSpan
{
MSpan *next; // in a span linked list
MSpan *prev; // in a span linked list
MSpan *allnext; // in the list of all spans
PageID start; // starting page number
uintptr npages; // number of pages in span
MLink *freelist; // list of free objects
uint32 ref; // number of allocated objects in this span
uint32 sizeclass; // size class
uint32 state; // MSpanInUse etc
byte *limit; // end of data in span
};
void runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages);
// 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_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;
MSpan empty;
int32 nfree;
};
void runtime_MCentral_Init(MCentral *c, int32 sizeclass);
int32 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **first);
void runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *first);
// 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 large; // free lists length >= MaxMHeapList
MSpan *allspans;
// span lookup
MSpan *map[1<<MHeapMap_Bits];
// range of addresses we might see in the heap
byte *bitmap;
uintptr bitmap_mapped;
byte *arena_start;
byte *arena_used;
byte *arena_end;
// central free lists for small size classes.
// the union makes sure that the MCentrals are
// spaced 64 bytes apart, so that each MCentral.Lock
// gets its own cache line.
union {
MCentral;
byte pad[64];
} central[NumSizeClasses];
FixAlloc spanalloc; // allocator for Span*
FixAlloc cachealloc; // allocator for MCache*
};
extern MHeap runtime_mheap;
void runtime_MHeap_Init(MHeap *h, void *(*allocator)(uintptr));
MSpan* runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct);
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_mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed);
int32 runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **s);
void runtime_gc(int32 force);
void runtime_markallocated(void *v, uintptr n, bool noptr);
void runtime_checkallocated(void *v, uintptr n);
void runtime_markfreed(void *v, uintptr n);
void runtime_checkfreed(void *v, uintptr n);
int32 runtime_checking;
void runtime_markspan(void *v, uintptr size, uintptr n, bool leftover);
void runtime_unmarkspan(void *v, uintptr size);
bool runtime_blockspecial(void*);
void runtime_setblockspecial(void*);
void runtime_purgecachedstats(M*);
enum
{
// flags to malloc
FlagNoPointers = 1<<0, // no pointers here
FlagNoProfiling = 1<<1, // must not profile
FlagNoGC = 1<<2, // must not free or scan for pointers
};
void runtime_Mprof_Init(void);
void runtime_MProf_Malloc(void*, uintptr);
void runtime_MProf_Free(void*, uintptr);
void runtime_MProf_Mark(void (*scan)(byte *, int64));
// Malloc profiling settings.
// Must match definition in extern.go.
enum {
MProf_None = 0,
MProf_Sample = 1,
MProf_All = 2,
};
extern int32 runtime_malloc_profile;
typedef struct Finalizer Finalizer;
struct Finalizer
{
Finalizer *next; // for use by caller of getfinalizer
void (*fn)(void*);
void *arg;
const struct __go_func_type *ft;
};
Finalizer* runtime_getfinalizer(void*, bool);
|