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. 4 5 // Memory allocator, based on tcmalloc. 6 // http://goog-perftools.sourceforge.net/doc/tcmalloc.html 7 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 14 // allocators. 15 // 16 // The allocator's data structures are: 17 // 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. 25 // 26 // Allocating a small object proceeds up a hierarchy of caches: 27 // 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. 32 // 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. 36 // 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 41 // the heap. 42 // 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. 47 // 48 // Freeing a small object proceeds up the same hierarchy: 49 // 50 // 1. Look up the size class for the object and add it to 51 // the MCache free list. 52 // 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. 55 // 56 // 3. If all the objects in a given span have returned to 57 // the MCentral list, return that span to the page heap. 58 // 59 // 4. If the heap has too much memory, return some to the 60 // operating system. 61 // 62 // TODO(rsc): Step 4 is not implemented. 63 // 64 // Allocating and freeing a large object uses the page heap 65 // directly, bypassing the MCache and MCentral free lists. 66 // 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 73 // zeroing this way: 74 // 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. 79 // 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, ...). 82 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 90 enum 91 { 92 PageShift = 12, 93 PageSize = 1<<PageShift, 94 PageMask = PageSize - 1, 95 }; 96 typedef uintptr PageID; // address >> PageShift 97 98 enum 99 { 100 // Computed constant. The definition of MaxSmallSize and the 101 // algorithm in msize.c produce some number of different allocation 102 // size classes. NumSizeClasses is that number. It's needed here 103 // because there are static arrays of this length; when msize runs its 104 // size choosing algorithm it double-checks that NumSizeClasses agrees. 105 NumSizeClasses = 61, 106 107 // Tunable constants. 108 MaxSmallSize = 32<<10, 109 110 FixAllocChunk = 128<<10, // Chunk size for FixAlloc 111 MaxMCacheListLen = 256, // Maximum objects on MCacheList 112 MaxMCacheSize = 2<<20, // Maximum bytes in one MCache 113 MaxMHeapList = 1<<(20 - PageShift), // Maximum page length for fixed-size list in MHeap. 114 HeapAllocChunk = 1<<20, // Chunk size for heap growth 115 116 // Number of bits in page to span calculations (4k pages). 117 // On 64-bit, we limit the arena to 128GB, or 37 bits. 118 // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address. 119 #if __SIZEOF_POINTER__ == 8 120 MHeapMap_Bits = 37 - PageShift, 121 #else 122 MHeapMap_Bits = 32 - PageShift, 123 #endif 124 125 // Max number of threads to run garbage collection. 126 // 2, 3, and 4 are all plausible maximums depending 127 // on the hardware details of the machine. The garbage 128 // collector scales well to 8 cpus. 129 MaxGcproc = 8, 130 }; 131 132 // Maximum memory allocation size, a hint for callers. 133 // This must be a #define instead of an enum because it 134 // is so large. 135 #if __SIZEOF_POINTER__ == 8 136 #define MaxMem (1ULL<<(MHeapMap_Bits+PageShift)) /* 128 GB */ 137 #else 138 #define MaxMem ((uintptr)-1) 139 #endif 140 141 // A generic linked list of blocks. (Typically the block is bigger than sizeof(MLink).) 142 struct MLink 143 { 144 MLink *next; 145 }; 146 147 // SysAlloc obtains a large chunk of zeroed memory from the 148 // operating system, typically on the order of a hundred kilobytes 149 // or a megabyte. If the pointer argument is non-nil, the caller 150 // wants a mapping there or nowhere. 151 // 152 // SysUnused notifies the operating system that the contents 153 // of the memory region are no longer needed and can be reused 154 // for other purposes. The program reserves the right to start 155 // accessing those pages in the future. 156 // 157 // SysFree returns it unconditionally; this is only used if 158 // an out-of-memory error has been detected midway through 159 // an allocation. It is okay if SysFree is a no-op. 160 // 161 // SysReserve reserves address space without allocating memory. 162 // If the pointer passed to it is non-nil, the caller wants the 163 // reservation there, but SysReserve can still choose another 164 // location if that one is unavailable. 165 // 166 // SysMap maps previously reserved address space for use. 167 168 void* runtime_SysAlloc(uintptr nbytes); 169 void runtime_SysFree(void *v, uintptr nbytes); 170 void runtime_SysUnused(void *v, uintptr nbytes); 171 void runtime_SysMap(void *v, uintptr nbytes); 172 void* runtime_SysReserve(void *v, uintptr nbytes); 173 174 // FixAlloc is a simple free-list allocator for fixed size objects. 175 // Malloc uses a FixAlloc wrapped around SysAlloc to manages its 176 // MCache and MSpan objects. 177 // 178 // Memory returned by FixAlloc_Alloc is not zeroed. 179 // The caller is responsible for locking around FixAlloc calls. 180 // Callers can keep state in the object but the first word is 181 // smashed by freeing and reallocating. 182 struct FixAlloc 183 { 184 uintptr size; 185 void *(*alloc)(uintptr); 186 void (*first)(void *arg, byte *p); // called first time p is returned 187 void *arg; 188 MLink *list; 189 byte *chunk; 190 uint32 nchunk; 191 uintptr inuse; // in-use bytes now 192 uintptr sys; // bytes obtained from system 193 }; 194 195 void runtime_FixAlloc_Init(FixAlloc *f, uintptr size, void *(*alloc)(uintptr), void (*first)(void*, byte*), void *arg); 196 void* runtime_FixAlloc_Alloc(FixAlloc *f); 197 void runtime_FixAlloc_Free(FixAlloc *f, void *p); 198 199 200 // Statistics. 201 // Shared with Go: if you edit this structure, also edit type MemStats in mem.go. 202 struct MStats 203 { 204 // General statistics. 205 uint64 alloc; // bytes allocated and still in use 206 uint64 total_alloc; // bytes allocated (even if freed) 207 uint64 sys; // bytes obtained from system (should be sum of xxx_sys below, no locking, approximate) 208 uint64 nlookup; // number of pointer lookups 209 uint64 nmalloc; // number of mallocs 210 uint64 nfree; // number of frees 211 212 // Statistics about malloc heap. 213 // protected by mheap.Lock 214 uint64 heap_alloc; // bytes allocated and still in use 215 uint64 heap_sys; // bytes obtained from system 216 uint64 heap_idle; // bytes in idle spans 217 uint64 heap_inuse; // bytes in non-idle spans 218 uint64 heap_released; // bytes released to the OS 219 uint64 heap_objects; // total number of allocated objects 220 221 // Statistics about allocation of low-level fixed-size structures. 222 // Protected by FixAlloc locks. 223 uint64 stacks_inuse; // bootstrap stacks 224 uint64 stacks_sys; 225 uint64 mspan_inuse; // MSpan structures 226 uint64 mspan_sys; 227 uint64 mcache_inuse; // MCache structures 228 uint64 mcache_sys; 229 uint64 buckhash_sys; // profiling bucket hash table 230 231 // Statistics about garbage collector. 232 // Protected by stopping the world during GC. 233 uint64 next_gc; // next GC (in heap_alloc time) 234 uint64 last_gc; // last GC (in absolute time) 235 uint64 pause_total_ns; 236 uint64 pause_ns[256]; 237 uint32 numgc; 238 bool enablegc; 239 bool debuggc; 240 241 // Statistics about allocation size classes. 242 struct { 243 uint32 size; 244 uint64 nmalloc; 245 uint64 nfree; 246 } by_size[NumSizeClasses]; 247 }; 248 249 extern MStats mstats 250 __asm__ (GOSYM_PREFIX "runtime.VmemStats"); 251 252 253 // Size classes. Computed and initialized by InitSizes. 254 // 255 // SizeToClass(0 <= n <= MaxSmallSize) returns the size class, 256 // 1 <= sizeclass < NumSizeClasses, for n. 257 // Size class 0 is reserved to mean "not small". 258 // 259 // class_to_size[i] = largest size in class i 260 // class_to_allocnpages[i] = number of pages to allocate when 261 // making new objects in class i 262 // class_to_transfercount[i] = number of objects to move when 263 // taking a bunch of objects out of the central lists 264 // and putting them in the thread free list. 265 266 int32 runtime_SizeToClass(int32); 267 extern int32 runtime_class_to_size[NumSizeClasses]; 268 extern int32 runtime_class_to_allocnpages[NumSizeClasses]; 269 extern int32 runtime_class_to_transfercount[NumSizeClasses]; 270 extern void runtime_InitSizes(void); 271 272 273 // Per-thread (in Go, per-M) cache for small objects. 274 // No locking needed because it is per-thread (per-M). 275 typedef struct MCacheList MCacheList; 276 struct MCacheList 277 { 278 MLink *list; 279 uint32 nlist; 280 uint32 nlistmin; 281 }; 282 283 struct MCache 284 { 285 MCacheList list[NumSizeClasses]; 286 uintptr size; 287 intptr local_cachealloc; // bytes allocated (or freed) from cache since last lock of heap 288 intptr local_objects; // objects allocated (or freed) from cache since last lock of heap 289 intptr local_alloc; // bytes allocated (or freed) since last lock of heap 290 uintptr local_total_alloc; // bytes allocated (even if freed) since last lock of heap 291 uintptr local_nmalloc; // number of mallocs since last lock of heap 292 uintptr local_nfree; // number of frees since last lock of heap 293 uintptr local_nlookup; // number of pointer lookups since last lock of heap 294 int32 next_sample; // trigger heap sample after allocating this many bytes 295 // Statistics about allocation size classes since last lock of heap 296 struct { 297 uintptr nmalloc; 298 uintptr nfree; 299 } local_by_size[NumSizeClasses]; 300 301 }; 302 303 void* runtime_MCache_Alloc(MCache *c, int32 sizeclass, uintptr size, int32 zeroed); 304 void runtime_MCache_Free(MCache *c, void *p, int32 sizeclass, uintptr size); 305 void runtime_MCache_ReleaseAll(MCache *c); 306 307 // MTypes describes the types of blocks allocated within a span. 308 // The compression field describes the layout of the data. 309 // 310 // MTypes_Empty: 311 // All blocks are free, or no type information is available for 312 // allocated blocks. 313 // The data field has no meaning. 314 // MTypes_Single: 315 // The span contains just one block. 316 // The data field holds the type information. 317 // The sysalloc field has no meaning. 318 // MTypes_Words: 319 // The span contains multiple blocks. 320 // The data field points to an array of type [NumBlocks]uintptr, 321 // and each element of the array holds the type of the corresponding 322 // block. 323 // MTypes_Bytes: 324 // The span contains at most seven different types of blocks. 325 // The data field points to the following structure: 326 // struct { 327 // type [8]uintptr // type[0] is always 0 328 // index [NumBlocks]byte 329 // } 330 // The type of the i-th block is: data.type[data.index[i]] 331 enum 332 { 333 MTypes_Empty = 0, 334 MTypes_Single = 1, 335 MTypes_Words = 2, 336 MTypes_Bytes = 3, 337 }; 338 struct MTypes 339 { 340 byte compression; // one of MTypes_* 341 bool sysalloc; // whether (void*)data is from runtime_SysAlloc 342 uintptr data; 343 }; 344 345 // An MSpan is a run of pages. 346 enum 347 { 348 MSpanInUse = 0, 349 MSpanFree, 350 MSpanListHead, 351 MSpanDead, 352 }; 353 struct MSpan 354 { 355 MSpan *next; // in a span linked list 356 MSpan *prev; // in a span linked list 357 PageID start; // starting page number 358 uintptr npages; // number of pages in span 359 MLink *freelist; // list of free objects 360 uint32 ref; // number of allocated objects in this span 361 int32 sizeclass; // size class 362 uintptr elemsize; // computed from sizeclass or from npages 363 uint32 state; // MSpanInUse etc 364 int64 unusedsince; // First time spotted by GC in MSpanFree state 365 uintptr npreleased; // number of pages released to the OS 366 byte *limit; // end of data in span 367 MTypes types; // types of allocated objects in this span 368 }; 369 370 void runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages); 371 372 // Every MSpan is in one doubly-linked list, 373 // either one of the MHeap's free lists or one of the 374 // MCentral's span lists. We use empty MSpan structures as list heads. 375 void runtime_MSpanList_Init(MSpan *list); 376 bool runtime_MSpanList_IsEmpty(MSpan *list); 377 void runtime_MSpanList_Insert(MSpan *list, MSpan *span); 378 void runtime_MSpanList_Remove(MSpan *span); // from whatever list it is in 379 380 381 // Central list of free objects of a given size. 382 struct MCentral 383 { 384 Lock; 385 int32 sizeclass; 386 MSpan nonempty; 387 MSpan empty; 388 int32 nfree; 389 }; 390 391 void runtime_MCentral_Init(MCentral *c, int32 sizeclass); 392 int32 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **first); 393 void runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *first); 394 void runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end); 395 396 // Main malloc heap. 397 // The heap itself is the "free[]" and "large" arrays, 398 // but all the other global data is here too. 399 struct MHeap 400 { 401 Lock; 402 MSpan free[MaxMHeapList]; // free lists of given length 403 MSpan large; // free lists length >= MaxMHeapList 404 MSpan **allspans; 405 uint32 nspan; 406 uint32 nspancap; 407 408 // span lookup 409 MSpan *map[1<<MHeapMap_Bits]; 410 411 // range of addresses we might see in the heap 412 byte *bitmap; 413 uintptr bitmap_mapped; 414 byte *arena_start; 415 byte *arena_used; 416 byte *arena_end; 417 418 // central free lists for small size classes. 419 // the union makes sure that the MCentrals are 420 // spaced CacheLineSize bytes apart, so that each MCentral.Lock 421 // gets its own cache line. 422 union { 423 MCentral; 424 byte pad[CacheLineSize]; 425 } central[NumSizeClasses]; 426 427 FixAlloc spanalloc; // allocator for Span* 428 FixAlloc cachealloc; // allocator for MCache* 429 }; 430 extern MHeap runtime_mheap; 431 432 void runtime_MHeap_Init(MHeap *h, void *(*allocator)(uintptr)); 433 MSpan* runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct, int32 zeroed); 434 void runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct); 435 MSpan* runtime_MHeap_Lookup(MHeap *h, void *v); 436 MSpan* runtime_MHeap_LookupMaybe(MHeap *h, void *v); 437 void runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *size, int32 *npages, int32 *nobj); 438 void* runtime_MHeap_SysAlloc(MHeap *h, uintptr n); 439 void runtime_MHeap_MapBits(MHeap *h); 440 void runtime_MHeap_Scavenger(void*); 441 442 void* runtime_mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed); 443 int32 runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **s); 444 void runtime_gc(int32 force); 445 void runtime_markallocated(void *v, uintptr n, bool noptr); 446 void runtime_checkallocated(void *v, uintptr n); 447 void runtime_markfreed(void *v, uintptr n); 448 void runtime_checkfreed(void *v, uintptr n); 449 extern int32 runtime_checking; 450 void runtime_markspan(void *v, uintptr size, uintptr n, bool leftover); 451 void runtime_unmarkspan(void *v, uintptr size); 452 bool runtime_blockspecial(void*); 453 void runtime_setblockspecial(void*, bool); 454 void runtime_purgecachedstats(MCache*); 455 void* runtime_new(const Type *); 456 #define runtime_cnew(T) runtime_new(T) 457 458 void runtime_settype(void*, uintptr); 459 void runtime_settype_flush(M*, bool); 460 void runtime_settype_sysfree(MSpan*); 461 uintptr runtime_gettype(void*); 462 463 enum 464 { 465 // flags to malloc 466 FlagNoPointers = 1<<0, // no pointers here 467 FlagNoProfiling = 1<<1, // must not profile 468 FlagNoGC = 1<<2, // must not free or scan for pointers 469 }; 470 471 typedef struct Obj Obj; 472 struct Obj 473 { 474 byte *p; // data pointer 475 uintptr n; // size of data in bytes 476 uintptr ti; // type info 477 }; 478 479 void runtime_MProf_Malloc(void*, uintptr); 480 void runtime_MProf_Free(void*, uintptr); 481 void runtime_MProf_GC(void); 482 void runtime_MProf_Mark(void (*addroot)(Obj)); 483 int32 runtime_gcprocs(void); 484 void runtime_helpgc(int32 nproc); 485 void runtime_gchelper(void); 486 487 struct __go_func_type; 488 bool runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_func_type **ft); 489 void runtime_walkfintab(void (*fn)(void*), void (*scan)(Obj)); 490 491 enum 492 { 493 TypeInfo_SingleObject = 0, 494 TypeInfo_Array = 1, 495 TypeInfo_Map = 2, 496 497 // Enables type information at the end of blocks allocated from heap 498 DebugTypeAtBlockEnd = 0, 499 }; 500 501 // defined in mgc0.go 502 void runtime_gc_m_ptr(Eface*); 503 void runtime_gc_itab_ptr(Eface*); 504 505 void runtime_memorydump(void); 506 507 void runtime_time_scan(void (*)(Obj)); 508 void runtime_trampoline_scan(void (*)(Obj)); 509