OSDN Git Service

runtime: Better detection of memory allocation request overflow.
[pf3gnuchains/gcc-fork.git] / libgo / runtime / malloc.h
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
89 enum
90 {
91         PageShift       = 12,
92         PageSize        = 1<<PageShift,
93         PageMask        = PageSize - 1,
94 };
95 typedef uintptr PageID;         // address >> PageShift
96
97 enum
98 {
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.
104         NumSizeClasses = 61,
105
106         // Tunable constants.
107         MaxSmallSize = 32<<10,
108
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
114
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
119         MHeapMap_Bits = 22,
120 #else
121         MHeapMap_Bits = 20,
122 #endif
123
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.
128         MaxGcproc = 4,
129 };
130
131 // Maximum memory allocation size, a hint for callers.
132 // This must be a #define instead of an enum because it
133 // is so large.
134 #if __SIZEOF_POINTER__ == 8
135 #define MaxMem  (16ULL<<30)     /* 16 GB */
136 #else
137 #define MaxMem  ((uintptr)-1)
138 #endif
139
140 // A generic linked list of blocks.  (Typically the block is bigger than sizeof(MLink).)
141 struct MLink
142 {
143         MLink *next;
144 };
145
146 // SysAlloc obtains a large chunk of zeroed memory from the
147 // operating system, typically on the order of a hundred kilobytes
148 // or a megabyte.  If the pointer argument is non-nil, the caller
149 // wants a mapping there or nowhere.
150 //
151 // SysUnused notifies the operating system that the contents
152 // of the memory region are no longer needed and can be reused
153 // for other purposes.  The program reserves the right to start
154 // accessing those pages in the future.
155 //
156 // SysFree returns it unconditionally; this is only used if
157 // an out-of-memory error has been detected midway through
158 // an allocation.  It is okay if SysFree is a no-op.
159 //
160 // SysReserve reserves address space without allocating memory.
161 // If the pointer passed to it is non-nil, the caller wants the
162 // reservation there, but SysReserve can still choose another
163 // location if that one is unavailable.
164 //
165 // SysMap maps previously reserved address space for use.
166
167 void*   runtime_SysAlloc(uintptr nbytes);
168 void    runtime_SysFree(void *v, uintptr nbytes);
169 void    runtime_SysUnused(void *v, uintptr nbytes);
170 void    runtime_SysMap(void *v, uintptr nbytes);
171 void*   runtime_SysReserve(void *v, uintptr nbytes);
172
173 // FixAlloc is a simple free-list allocator for fixed size objects.
174 // Malloc uses a FixAlloc wrapped around SysAlloc to manages its
175 // MCache and MSpan objects.
176 //
177 // Memory returned by FixAlloc_Alloc is not zeroed.
178 // The caller is responsible for locking around FixAlloc calls.
179 // Callers can keep state in the object but the first word is
180 // smashed by freeing and reallocating.
181 struct FixAlloc
182 {
183         uintptr size;
184         void *(*alloc)(uintptr);
185         void (*first)(void *arg, byte *p);      // called first time p is returned
186         void *arg;
187         MLink *list;
188         byte *chunk;
189         uint32 nchunk;
190         uintptr inuse;  // in-use bytes now
191         uintptr sys;    // bytes obtained from system
192 };
193
194 void    runtime_FixAlloc_Init(FixAlloc *f, uintptr size, void *(*alloc)(uintptr), void (*first)(void*, byte*), void *arg);
195 void*   runtime_FixAlloc_Alloc(FixAlloc *f);
196 void    runtime_FixAlloc_Free(FixAlloc *f, void *p);
197
198
199 // Statistics.
200 // Shared with Go: if you edit this structure, also edit extern.go.
201 struct MStats
202 {
203         // General statistics.
204         uint64  alloc;          // bytes allocated and still in use
205         uint64  total_alloc;    // bytes allocated (even if freed)
206         uint64  sys;            // bytes obtained from system (should be sum of xxx_sys below, no locking, approximate)
207         uint64  nlookup;        // number of pointer lookups
208         uint64  nmalloc;        // number of mallocs
209         uint64  nfree;  // number of frees
210
211         // Statistics about malloc heap.
212         // protected by mheap.Lock
213         uint64  heap_alloc;     // bytes allocated and still in use
214         uint64  heap_sys;       // bytes obtained from system
215         uint64  heap_idle;      // bytes in idle spans
216         uint64  heap_inuse;     // bytes in non-idle spans
217         uint64  heap_released;  // bytes released to the OS
218         uint64  heap_objects;   // total number of allocated objects
219
220         // Statistics about allocation of low-level fixed-size structures.
221         // Protected by FixAlloc locks.
222         uint64  stacks_inuse;   // bootstrap stacks
223         uint64  stacks_sys;
224         uint64  mspan_inuse;    // MSpan structures
225         uint64  mspan_sys;
226         uint64  mcache_inuse;   // MCache structures
227         uint64  mcache_sys;
228         uint64  buckhash_sys;   // profiling bucket hash table
229
230         // Statistics about garbage collector.
231         // Protected by stopping the world during GC.
232         uint64  next_gc;        // next GC (in heap_alloc time)
233         uint64  last_gc;        // last GC (in absolute time)
234         uint64  pause_total_ns;
235         uint64  pause_ns[256];
236         uint32  numgc;
237         bool    enablegc;
238         bool    debuggc;
239
240         // Statistics about allocation size classes.
241         struct {
242                 uint32 size;
243                 uint64 nmalloc;
244                 uint64 nfree;
245         } by_size[NumSizeClasses];
246 };
247
248 extern MStats mstats
249   __asm__ ("runtime.VmemStats");
250
251
252 // Size classes.  Computed and initialized by InitSizes.
253 //
254 // SizeToClass(0 <= n <= MaxSmallSize) returns the size class,
255 //      1 <= sizeclass < NumSizeClasses, for n.
256 //      Size class 0 is reserved to mean "not small".
257 //
258 // class_to_size[i] = largest size in class i
259 // class_to_allocnpages[i] = number of pages to allocate when
260 //      making new objects in class i
261 // class_to_transfercount[i] = number of objects to move when
262 //      taking a bunch of objects out of the central lists
263 //      and putting them in the thread free list.
264
265 int32   runtime_SizeToClass(int32);
266 extern  int32   runtime_class_to_size[NumSizeClasses];
267 extern  int32   runtime_class_to_allocnpages[NumSizeClasses];
268 extern  int32   runtime_class_to_transfercount[NumSizeClasses];
269 extern  void    runtime_InitSizes(void);
270
271
272 // Per-thread (in Go, per-M) cache for small objects.
273 // No locking needed because it is per-thread (per-M).
274 typedef struct MCacheList MCacheList;
275 struct MCacheList
276 {
277         MLink *list;
278         uint32 nlist;
279         uint32 nlistmin;
280 };
281
282 struct MCache
283 {
284         MCacheList list[NumSizeClasses];
285         uint64 size;
286         int64 local_cachealloc; // bytes allocated (or freed) from cache since last lock of heap
287         int64 local_objects;    // objects allocated (or freed) from cache since last lock of heap
288         int64 local_alloc;      // bytes allocated (or freed) since last lock of heap
289         int64 local_total_alloc;        // bytes allocated (even if freed) since last lock of heap
290         int64 local_nmalloc;    // number of mallocs since last lock of heap
291         int64 local_nfree;      // number of frees since last lock of heap
292         int64 local_nlookup;    // number of pointer lookups since last lock of heap
293         int32 next_sample;      // trigger heap sample after allocating this many bytes
294         // Statistics about allocation size classes since last lock of heap
295         struct {
296                 int64 nmalloc;
297                 int64 nfree;
298         } local_by_size[NumSizeClasses];
299
300 };
301
302 void*   runtime_MCache_Alloc(MCache *c, int32 sizeclass, uintptr size, int32 zeroed);
303 void    runtime_MCache_Free(MCache *c, void *p, int32 sizeclass, uintptr size);
304 void    runtime_MCache_ReleaseAll(MCache *c);
305
306 // An MSpan is a run of pages.
307 enum
308 {
309         MSpanInUse = 0,
310         MSpanFree,
311         MSpanListHead,
312         MSpanDead,
313 };
314 struct MSpan
315 {
316         MSpan   *next;          // in a span linked list
317         MSpan   *prev;          // in a span linked list
318         MSpan   *allnext;       // in the list of all spans
319         PageID  start;          // starting page number
320         uintptr npages;         // number of pages in span
321         MLink   *freelist;      // list of free objects
322         uint32  ref;            // number of allocated objects in this span
323         uint32  sizeclass;      // size class
324         uint32  state;          // MSpanInUse etc
325         int64   unusedsince;    // First time spotted by GC in MSpanFree state
326         uintptr npreleased;     // number of pages released to the OS
327         byte    *limit;         // end of data in span
328 };
329
330 void    runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages);
331
332 // Every MSpan is in one doubly-linked list,
333 // either one of the MHeap's free lists or one of the
334 // MCentral's span lists.  We use empty MSpan structures as list heads.
335 void    runtime_MSpanList_Init(MSpan *list);
336 bool    runtime_MSpanList_IsEmpty(MSpan *list);
337 void    runtime_MSpanList_Insert(MSpan *list, MSpan *span);
338 void    runtime_MSpanList_Remove(MSpan *span);  // from whatever list it is in
339
340
341 // Central list of free objects of a given size.
342 struct MCentral
343 {
344         Lock;
345         int32 sizeclass;
346         MSpan nonempty;
347         MSpan empty;
348         int32 nfree;
349 };
350
351 void    runtime_MCentral_Init(MCentral *c, int32 sizeclass);
352 int32   runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **first);
353 void    runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *first);
354
355 // Main malloc heap.
356 // The heap itself is the "free[]" and "large" arrays,
357 // but all the other global data is here too.
358 struct MHeap
359 {
360         Lock;
361         MSpan free[MaxMHeapList];       // free lists of given length
362         MSpan large;                    // free lists length >= MaxMHeapList
363         MSpan *allspans;
364
365         // span lookup
366         MSpan *map[1<<MHeapMap_Bits];
367
368         // range of addresses we might see in the heap
369         byte *bitmap;
370         uintptr bitmap_mapped;
371         byte *arena_start;
372         byte *arena_used;
373         byte *arena_end;
374
375         // central free lists for small size classes.
376         // the union makes sure that the MCentrals are
377         // spaced CacheLineSize bytes apart, so that each MCentral.Lock
378         // gets its own cache line.
379         union {
380                 MCentral;
381                 byte pad[CacheLineSize];
382         } central[NumSizeClasses];
383
384         FixAlloc spanalloc;     // allocator for Span*
385         FixAlloc cachealloc;    // allocator for MCache*
386 };
387 extern MHeap runtime_mheap;
388
389 void    runtime_MHeap_Init(MHeap *h, void *(*allocator)(uintptr));
390 MSpan*  runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct);
391 void    runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct);
392 MSpan*  runtime_MHeap_Lookup(MHeap *h, void *v);
393 MSpan*  runtime_MHeap_LookupMaybe(MHeap *h, void *v);
394 void    runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *size, int32 *npages, int32 *nobj);
395 void*   runtime_MHeap_SysAlloc(MHeap *h, uintptr n);
396 void    runtime_MHeap_MapBits(MHeap *h);
397 void    runtime_MHeap_Scavenger(void*);
398
399 void*   runtime_mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed);
400 int32   runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **s);
401 void    runtime_gc(int32 force);
402 void    runtime_markallocated(void *v, uintptr n, bool noptr);
403 void    runtime_checkallocated(void *v, uintptr n);
404 void    runtime_markfreed(void *v, uintptr n);
405 void    runtime_checkfreed(void *v, uintptr n);
406 int32   runtime_checking;
407 void    runtime_markspan(void *v, uintptr size, uintptr n, bool leftover);
408 void    runtime_unmarkspan(void *v, uintptr size);
409 bool    runtime_blockspecial(void*);
410 void    runtime_setblockspecial(void*, bool);
411 void    runtime_purgecachedstats(M*);
412
413 enum
414 {
415         // flags to malloc
416         FlagNoPointers = 1<<0,  // no pointers here
417         FlagNoProfiling = 1<<1, // must not profile
418         FlagNoGC = 1<<2,        // must not free or scan for pointers
419 };
420
421 void    runtime_MProf_Malloc(void*, uintptr);
422 void    runtime_MProf_Free(void*, uintptr);
423 void    runtime_MProf_GC(void);
424 void    runtime_MProf_Mark(void (*scan)(byte *, int64));
425 int32   runtime_helpgc(bool*);
426 void    runtime_gchelper(void);
427
428 struct __go_func_type;
429 bool    runtime_getfinalizer(void *p, bool del, void (**fn)(void*), const struct __go_func_type **ft);
430 void    runtime_walkfintab(void (*fn)(void*), void (*scan)(byte *, int64));