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 // See malloc.h for overview.
7 // TODO(rsc): double-check stats.
16 #include "go-string.h"
17 #include "interface.h"
19 typedef struct __go_empty_interface Eface;
20 typedef struct __go_type_descriptor Type;
21 typedef struct __go_func_type FuncType;
24 extern MStats mstats; // defined in extern.go
26 extern volatile int32 runtime_MemProfileRate
27 __asm__ ("libgo_runtime.runtime.MemProfileRate");
29 // Same algorithm from chan.c, but a different
30 // instance of the static uint32 x.
31 // Not protected by a lock - let the threads use
32 // the same random number if they like.
36 static uint32 x = 0x49f6428aUL;
44 // Allocate an object of at least size bytes.
45 // Small objects are allocated from the per-thread cache's free lists.
46 // Large objects (> 32 kB) are allocated straight from the heap.
48 runtime_mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
50 int32 sizeclass, rate;
56 if(!__sync_bool_compare_and_swap(&m->mallocing, 0, 1))
57 runtime_throw("malloc/free - deadlock");
62 if(size <= MaxSmallSize) {
63 // Allocate from mcache free lists.
64 sizeclass = runtime_SizeToClass(size);
65 size = runtime_class_to_size[sizeclass];
67 v = runtime_MCache_Alloc(c, sizeclass, size, zeroed);
69 runtime_throw("out of memory");
71 mstats.total_alloc += size;
72 mstats.by_size[sizeclass].nmalloc++;
74 // TODO(rsc): Report tracebacks for very large allocations.
76 // Allocate directly from heap.
77 npages = size >> PageShift;
78 if((size & PageMask) != 0)
80 s = runtime_MHeap_Alloc(&runtime_mheap, npages, 0, 1);
82 runtime_throw("out of memory");
83 size = npages<<PageShift;
85 mstats.total_alloc += size;
86 v = (void*)(s->start << PageShift);
88 // setup for mark sweep
89 runtime_markspan(v, 0, 0, true);
91 if(!(flag & FlagNoGC))
92 runtime_markallocated(v, size, (flag&FlagNoPointers) != 0);
94 __sync_bool_compare_and_swap(&m->mallocing, 1, 0);
96 if(__sync_bool_compare_and_swap(&m->gcing, 1, 0)) {
97 if(!(flag & FlagNoProfiling))
98 __go_run_goroutine_gc(0);
100 // We are being called from the profiler. Tell it
101 // to invoke the garbage collector when it is
102 // done. No need to use a sync function here.
103 m->gcing_for_prof = 1;
107 if(!(flag & FlagNoProfiling) && (rate = runtime_MemProfileRate) > 0) {
108 if(size >= (uint32) rate)
110 if((uint32) m->mcache->next_sample > size)
111 m->mcache->next_sample -= size;
113 // pick next profile time
114 if(rate > 0x3fffffff) // make 2*rate not overflow
116 m->mcache->next_sample = fastrand1() % (2*rate);
118 runtime_setblockspecial(v);
119 runtime_MProf_Malloc(v, size);
123 if(dogc && mstats.heap_alloc >= mstats.next_gc)
129 __go_alloc(uintptr size)
131 return runtime_mallocgc(size, 0, 0, 1);
134 // Free the object whose base pointer is v.
147 // If you change this also change mgc0.c:/^sweepspan,
148 // which has a copy of the guts of free.
150 if(!__sync_bool_compare_and_swap(&m->mallocing, 0, 1))
151 runtime_throw("malloc/free - deadlock");
153 if(!runtime_mlookup(v, nil, nil, &s)) {
154 // runtime_printf("free %p: not an allocated block\n", v);
155 runtime_throw("free runtime_mlookup");
157 prof = runtime_blockspecial(v);
159 // Find size class for v.
160 sizeclass = s->sizeclass;
163 size = s->npages<<PageShift;
164 *(uintptr*)(s->start<<PageShift) = 1; // mark as "needs to be zeroed"
165 // Must mark v freed before calling unmarkspan and MHeap_Free:
166 // they might coalesce v into other spans and change the bitmap further.
167 runtime_markfreed(v, size);
168 runtime_unmarkspan(v, 1<<PageShift);
169 runtime_MHeap_Free(&runtime_mheap, s, 1);
173 size = runtime_class_to_size[sizeclass];
174 if(size > (int32)sizeof(uintptr))
175 ((uintptr*)v)[1] = 1; // mark as "needs to be zeroed"
176 // Must mark v freed before calling MCache_Free:
177 // it might coalesce v and other blocks into a bigger span
178 // and change the bitmap further.
179 runtime_markfreed(v, size);
180 mstats.by_size[sizeclass].nfree++;
181 runtime_MCache_Free(c, v, sizeclass, size);
183 mstats.alloc -= size;
185 runtime_MProf_Free(v, size);
187 __sync_bool_compare_and_swap(&m->mallocing, 1, 0);
189 if(__sync_bool_compare_and_swap(&m->gcing, 1, 0))
190 __go_run_goroutine_gc(1);
194 runtime_mlookup(void *v, byte **base, uintptr *size, MSpan **sp)
201 s = runtime_MHeap_LookupMaybe(&runtime_mheap, v);
205 runtime_checkfreed(v, 1);
213 p = (byte*)((uintptr)s->start<<PageShift);
214 if(s->sizeclass == 0) {
219 *size = s->npages<<PageShift;
223 if((byte*)v >= (byte*)s->limit) {
224 // pointers past the last block do not count as pointers.
228 n = runtime_class_to_size[s->sizeclass];
229 i = ((byte*)v - p)/n;
239 runtime_allocmcache(void)
243 if(!__sync_bool_compare_and_swap(&m->mallocing, 0, 1))
244 runtime_throw("allocmcache - deadlock");
246 runtime_lock(&runtime_mheap);
247 c = runtime_FixAlloc_Alloc(&runtime_mheap.cachealloc);
249 // Clear the free list used by FixAlloc; assume the rest is zeroed.
250 c->list[0].list = nil;
252 mstats.mcache_inuse = runtime_mheap.cachealloc.inuse;
253 mstats.mcache_sys = runtime_mheap.cachealloc.sys;
254 runtime_unlock(&runtime_mheap);
256 __sync_bool_compare_and_swap(&m->mallocing, 1, 0);
257 if(__sync_bool_compare_and_swap(&m->gcing, 1, 0))
258 __go_run_goroutine_gc(2);
263 extern int32 runtime_sizeof_C_MStats
264 __asm__ ("libgo_runtime.runtime.Sizeof_C_MStats");
266 #define MaxArena32 (2U<<30)
269 runtime_mallocinit(void)
272 uintptr arena_size, bitmap_size;
275 runtime_sizeof_C_MStats = sizeof(MStats);
279 // Set up the allocation arena, a contiguous area of memory where
280 // allocated data will be found. The arena begins with a bitmap large
281 // enough to hold 4 bits per allocated word.
282 if(sizeof(void*) == 8) {
283 // On a 64-bit machine, allocate from a single contiguous reservation.
284 // 16 GB should be big enough for now.
286 // The code will work with the reservation at any address, but ask
287 // SysReserve to use 0x000000f800000000 if possible.
288 // Allocating a 16 GB region takes away 36 bits, and the amd64
289 // doesn't let us choose the top 17 bits, so that leaves the 11 bits
290 // in the middle of 0x00f8 for us to choose. Choosing 0x00f8 means
291 // that the valid memory addresses will begin 0x00f8, 0x00f9, 0x00fa, 0x00fb.
292 // None of the bytes f8 f9 fa fb can appear in valid UTF-8, and
293 // they are otherwise as far from ff (likely a common byte) as possible.
294 // Choosing 0x00 for the leading 6 bits was more arbitrary, but it
295 // is not a common ASCII code point either. Using 0x11f8 instead
296 // caused out of memory errors on OS X during thread allocations.
297 // These choices are both for debuggability and to reduce the
298 // odds of the conservative garbage collector not collecting memory
299 // because some non-pointer block of memory had a bit pattern
300 // that matched a memory address.
302 // Actually we reserve 17 GB (because the bitmap ends up being 1 GB)
303 // but it hardly matters: fc is not valid UTF-8 either, and we have to
304 // allocate 15 GB before we get that far.
305 arena_size = (uintptr)(16LL<<30);
306 bitmap_size = arena_size / (sizeof(void*)*8/4);
307 p = runtime_SysReserve((void*)(0x00f8ULL<<32), bitmap_size + arena_size);
309 runtime_throw("runtime: cannot reserve arena virtual address space");
311 // On a 32-bit machine, we can't typically get away
312 // with a giant virtual address space reservation.
313 // Instead we map the memory information bitmap
314 // immediately after the data segment, large enough
315 // to handle another 2GB of mappings (256 MB),
316 // along with a reservation for another 512 MB of memory.
317 // When that gets used up, we'll start asking the kernel
318 // for any memory anywhere and hope it's in the 2GB
319 // following the bitmap (presumably the executable begins
320 // near the bottom of memory, so we'll have to use up
321 // most of memory before the kernel resorts to giving out
322 // memory before the beginning of the text segment).
324 // Alternatively we could reserve 512 MB bitmap, enough
325 // for 4GB of mappings, and then accept any memory the
326 // kernel threw at us, but normally that's a waste of 512 MB
327 // of address space, which is probably too much in a 32-bit world.
328 bitmap_size = MaxArena32 / (sizeof(void*)*8/4);
329 arena_size = 512<<20;
331 // SysReserve treats the address we ask for, end, as a hint,
332 // not as an absolute requirement. If we ask for the end
333 // of the data segment but the operating system requires
334 // a little more space before we can start allocating, it will
335 // give out a slightly higher pointer. That's fine.
336 // Run with what we get back.
337 p = runtime_SysReserve(end, bitmap_size + arena_size);
339 runtime_throw("runtime: cannot reserve arena virtual address space");
341 if((uintptr)p & (((uintptr)1<<PageShift)-1))
342 runtime_throw("runtime: SysReserve returned unaligned address");
344 runtime_mheap.bitmap = p;
345 runtime_mheap.arena_start = p + bitmap_size;
346 runtime_mheap.arena_used = runtime_mheap.arena_start;
347 runtime_mheap.arena_end = runtime_mheap.arena_start + arena_size;
349 // Initialize the rest of the allocator.
350 runtime_MHeap_Init(&runtime_mheap, runtime_SysAlloc);
351 m->mcache = runtime_allocmcache();
353 // Initialize malloc profiling.
354 runtime_Mprof_Init();
356 // Initialize finalizer.
357 runtime_initfintab();
360 runtime_free(runtime_malloc(1));
364 runtime_MHeap_SysAlloc(MHeap *h, uintptr n)
368 if(n <= (uintptr)(h->arena_end - h->arena_used)) {
369 // Keep taking from our reservation.
371 runtime_SysMap(p, n);
373 runtime_MHeap_MapBits(h);
377 // On 64-bit, our reservation is all we have.
378 if(sizeof(void*) == 8)
381 // On 32-bit, once the reservation is gone we can
382 // try to get memory at a location chosen by the OS
383 // and hope that it is in the range we allocated bitmap for.
384 p = runtime_SysAlloc(n);
388 if(p < h->arena_start || (uintptr)(p+n - h->arena_start) >= MaxArena32) {
389 runtime_printf("runtime: memory allocated by OS not in usable range");
390 runtime_SysFree(p, n);
394 if(p+n > h->arena_used) {
396 if(h->arena_used > h->arena_end)
397 h->arena_end = h->arena_used;
398 runtime_MHeap_MapBits(h);
407 runtime_mal(uintptr n)
409 return runtime_mallocgc(n, 0, 1, 1);
412 func new(n uint32) (ret *uint8) {
413 ret = runtime_mal(n);
416 func Alloc(n uintptr) (p *byte) {
417 p = runtime_malloc(n);
424 func Lookup(p *byte) (base *byte, size uintptr) {
425 runtime_mlookup(p, &base, &size, nil);
432 func SetFinalizer(obj Eface, finalizer Eface) {
437 if(obj.__type_descriptor == nil) {
438 // runtime_printf("runtime.SetFinalizer: first argument is nil interface\n");
440 runtime_throw("runtime.SetFinalizer");
442 if(obj.__type_descriptor->__code != GO_PTR) {
443 // runtime_printf("runtime.SetFinalizer: first argument is %S, not pointer\n", *obj.type->string);
446 if(!runtime_mlookup(obj.__object, &base, &size, nil) || obj.__object != base) {
447 // runtime_printf("runtime.SetFinalizer: pointer not at beginning of allocated block\n");
451 if(finalizer.__type_descriptor != nil) {
452 if(finalizer.__type_descriptor->__code != GO_FUNC) {
454 // runtime_printf("runtime.SetFinalizer: second argument is %S, not func(%S)\n", *finalizer.type->string, *obj.type->string);
457 ft = (const FuncType*)finalizer.__type_descriptor;
458 if(ft->__dotdotdot || ft->__in.__count != 1 || !__go_type_descriptors_equal(*(Type**)ft->__in.__values, obj.__type_descriptor))
461 if(runtime_getfinalizer(obj.__object, 0)) {
462 // runtime_printf("runtime.SetFinalizer: finalizer already set");
466 runtime_addfinalizer(obj.__object, finalizer.__type_descriptor != nil ? *(void**)finalizer.__object : nil, ft);