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.
7 // See malloc.h for overview.
9 // When a MSpan is in the heap free list, state == MSpanFree
10 // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
12 // When a MSpan is allocated, state == MSpanInUse
13 // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
19 static MSpan
*MHeap_AllocLocked(MHeap
*, uintptr
, int32
);
20 static bool MHeap_Grow(MHeap
*, uintptr
);
21 static void MHeap_FreeLocked(MHeap
*, MSpan
*);
22 static MSpan
*MHeap_AllocLarge(MHeap
*, uintptr
);
23 static MSpan
*BestFit(MSpan
*, uintptr
, MSpan
*);
26 RecordSpan(void *vh
, byte
*p
)
33 s
->allnext
= h
->allspans
;
37 // Initialize the heap; fetch memory using alloc.
39 runtime_MHeap_Init(MHeap
*h
, void *(*alloc
)(uintptr
))
43 runtime_FixAlloc_Init(&h
->spanalloc
, sizeof(MSpan
), alloc
, RecordSpan
, h
);
44 runtime_FixAlloc_Init(&h
->cachealloc
, sizeof(MCache
), alloc
, nil
, nil
);
45 // h->mapcache needs no init
46 for(i
=0; i
<nelem(h
->free
); i
++)
47 runtime_MSpanList_Init(&h
->free
[i
]);
48 runtime_MSpanList_Init(&h
->large
);
49 for(i
=0; i
<nelem(h
->central
); i
++)
50 runtime_MCentral_Init(&h
->central
[i
], i
);
53 // Allocate a new span of npage pages from the heap
54 // and record its size class in the HeapMap and HeapMapCache.
56 runtime_MHeap_Alloc(MHeap
*h
, uintptr npage
, int32 sizeclass
, int32 acct
)
61 runtime_purgecachedstats(runtime_m());
62 s
= MHeap_AllocLocked(h
, npage
, sizeclass
);
64 mstats
.heap_inuse
+= npage
<<PageShift
;
66 mstats
.heap_objects
++;
67 mstats
.heap_alloc
+= npage
<<PageShift
;
75 MHeap_AllocLocked(MHeap
*h
, uintptr npage
, int32 sizeclass
)
81 // Try in fixed-size lists up to max.
82 for(n
=npage
; n
< nelem(h
->free
); n
++) {
83 if(!runtime_MSpanList_IsEmpty(&h
->free
[n
])) {
89 // Best fit in list of large spans.
90 if((s
= MHeap_AllocLarge(h
, npage
)) == nil
) {
91 if(!MHeap_Grow(h
, npage
))
93 if((s
= MHeap_AllocLarge(h
, npage
)) == nil
)
99 if(s
->state
!= MSpanFree
)
100 runtime_throw("MHeap_AllocLocked - MSpan not free");
101 if(s
->npages
< npage
)
102 runtime_throw("MHeap_AllocLocked - bad npages");
103 runtime_MSpanList_Remove(s
);
104 s
->state
= MSpanInUse
;
105 mstats
.heap_idle
-= s
->npages
<<PageShift
;
106 mstats
.heap_released
-= s
->npreleased
<<PageShift
;
109 if(s
->npages
> npage
) {
110 // Trim extra and put it back in the heap.
111 t
= runtime_FixAlloc_Alloc(&h
->spanalloc
);
112 mstats
.mspan_inuse
= h
->spanalloc
.inuse
;
113 mstats
.mspan_sys
= h
->spanalloc
.sys
;
114 runtime_MSpan_Init(t
, s
->start
+ npage
, s
->npages
- npage
);
117 if(sizeof(void*) == 8)
118 p
-= ((uintptr
)h
->arena_start
>>PageShift
);
122 h
->map
[p
+t
->npages
-1] = t
;
123 *(uintptr
*)(t
->start
<<PageShift
) = *(uintptr
*)(s
->start
<<PageShift
); // copy "needs zeroing" mark
124 t
->state
= MSpanInUse
;
125 MHeap_FreeLocked(h
, t
);
128 if(*(uintptr
*)(s
->start
<<PageShift
) != 0)
129 runtime_memclr((byte
*)(s
->start
<<PageShift
), s
->npages
<<PageShift
);
131 // Record span info, because gc needs to be
132 // able to map interior pointer to containing span.
133 s
->sizeclass
= sizeclass
;
135 if(sizeof(void*) == 8)
136 p
-= ((uintptr
)h
->arena_start
>>PageShift
);
137 for(n
=0; n
<npage
; n
++)
142 // Allocate a span of exactly npage pages from the list of large spans.
144 MHeap_AllocLarge(MHeap
*h
, uintptr npage
)
146 return BestFit(&h
->large
, npage
, nil
);
149 // Search list for smallest span with >= npage pages.
150 // If there are multiple smallest spans, take the one
151 // with the earliest starting address.
153 BestFit(MSpan
*list
, uintptr npage
, MSpan
*best
)
157 for(s
=list
->next
; s
!= list
; s
=s
->next
) {
158 if(s
->npages
< npage
)
161 || s
->npages
< best
->npages
162 || (s
->npages
== best
->npages
&& s
->start
< best
->start
))
168 // Try to add at least npage pages of memory to the heap,
169 // returning whether it worked.
171 MHeap_Grow(MHeap
*h
, uintptr npage
)
178 // Ask for a big chunk, to reduce the number of mappings
179 // the operating system needs to track; also amortizes
180 // the overhead of an operating system mapping.
181 // Allocate a multiple of 64kB (16 pages).
182 npage
= (npage
+15)&~15;
183 ask
= npage
<<PageShift
;
184 if(ask
< HeapAllocChunk
)
185 ask
= HeapAllocChunk
;
187 v
= runtime_MHeap_SysAlloc(h
, ask
);
189 if(ask
> (npage
<<PageShift
)) {
190 ask
= npage
<<PageShift
;
191 v
= runtime_MHeap_SysAlloc(h
, ask
);
194 runtime_printf("runtime: out of memory: cannot allocate %llu-byte block (%llu in use)\n", (unsigned long long)ask
, (unsigned long long)mstats
.heap_sys
);
198 mstats
.heap_sys
+= ask
;
200 // Create a fake "in use" span and free it, so that the
201 // right coalescing happens.
202 s
= runtime_FixAlloc_Alloc(&h
->spanalloc
);
203 mstats
.mspan_inuse
= h
->spanalloc
.inuse
;
204 mstats
.mspan_sys
= h
->spanalloc
.sys
;
205 runtime_MSpan_Init(s
, (uintptr
)v
>>PageShift
, ask
>>PageShift
);
207 if(sizeof(void*) == 8)
208 p
-= ((uintptr
)h
->arena_start
>>PageShift
);
210 h
->map
[p
+ s
->npages
- 1] = s
;
211 s
->state
= MSpanInUse
;
212 MHeap_FreeLocked(h
, s
);
216 // Look up the span at the given address.
217 // Address is guaranteed to be in map
218 // and is guaranteed to be start or end of span.
220 runtime_MHeap_Lookup(MHeap
*h
, void *v
)
225 if(sizeof(void*) == 8)
226 p
-= (uintptr
)h
->arena_start
;
227 return h
->map
[p
>> PageShift
];
230 // Look up the span at the given address.
231 // Address is *not* guaranteed to be in map
232 // and may be anywhere in the span.
233 // Map entries for the middle of a span are only
234 // valid for allocated spans. Free spans may have
235 // other garbage in their middles, so we have to
238 runtime_MHeap_LookupMaybe(MHeap
*h
, void *v
)
243 if((byte
*)v
< h
->arena_start
|| (byte
*)v
>= h
->arena_used
)
245 p
= (uintptr
)v
>>PageShift
;
247 if(sizeof(void*) == 8)
248 q
-= (uintptr
)h
->arena_start
>> PageShift
;
250 if(s
== nil
|| p
< s
->start
|| p
- s
->start
>= s
->npages
)
252 if(s
->state
!= MSpanInUse
)
257 // Free the span back into the heap.
259 runtime_MHeap_Free(MHeap
*h
, MSpan
*s
, int32 acct
)
262 runtime_purgecachedstats(runtime_m());
263 mstats
.heap_inuse
-= s
->npages
<<PageShift
;
265 mstats
.heap_alloc
-= s
->npages
<<PageShift
;
266 mstats
.heap_objects
--;
268 MHeap_FreeLocked(h
, s
);
273 MHeap_FreeLocked(MHeap
*h
, MSpan
*s
)
279 if(s
->state
!= MSpanInUse
|| s
->ref
!= 0) {
280 // runtime_printf("MHeap_FreeLocked - span %p ptr %p state %d ref %d\n", s, s->start<<PageShift, s->state, s->ref);
281 runtime_throw("MHeap_FreeLocked - invalid free");
283 mstats
.heap_idle
+= s
->npages
<<PageShift
;
284 s
->state
= MSpanFree
;
287 runtime_MSpanList_Remove(s
);
288 sp
= (uintptr
*)(s
->start
<<PageShift
);
290 // Coalesce with earlier, later spans.
292 if(sizeof(void*) == 8)
293 p
-= (uintptr
)h
->arena_start
>> PageShift
;
294 if(p
> 0 && (t
= h
->map
[p
-1]) != nil
&& t
->state
!= MSpanInUse
) {
295 tp
= (uintptr
*)(t
->start
<<PageShift
);
296 *tp
|= *sp
; // propagate "needs zeroing" mark
298 s
->npages
+= t
->npages
;
299 s
->npreleased
= t
->npreleased
; // absorb released pages
302 runtime_MSpanList_Remove(t
);
303 t
->state
= MSpanDead
;
304 runtime_FixAlloc_Free(&h
->spanalloc
, t
);
305 mstats
.mspan_inuse
= h
->spanalloc
.inuse
;
306 mstats
.mspan_sys
= h
->spanalloc
.sys
;
308 if(p
+s
->npages
< nelem(h
->map
) && (t
= h
->map
[p
+s
->npages
]) != nil
&& t
->state
!= MSpanInUse
) {
309 tp
= (uintptr
*)(t
->start
<<PageShift
);
310 *sp
|= *tp
; // propagate "needs zeroing" mark
311 s
->npages
+= t
->npages
;
312 s
->npreleased
+= t
->npreleased
;
313 h
->map
[p
+ s
->npages
- 1] = s
;
314 runtime_MSpanList_Remove(t
);
315 t
->state
= MSpanDead
;
316 runtime_FixAlloc_Free(&h
->spanalloc
, t
);
317 mstats
.mspan_inuse
= h
->spanalloc
.inuse
;
318 mstats
.mspan_sys
= h
->spanalloc
.sys
;
321 // Insert s into appropriate list.
322 if(s
->npages
< nelem(h
->free
))
323 runtime_MSpanList_Insert(&h
->free
[s
->npages
], s
);
325 runtime_MSpanList_Insert(&h
->large
, s
);
328 // Release (part of) unused memory to OS.
329 // Goroutine created at startup.
332 runtime_MHeap_Scavenger(void* dummy
)
336 uint64 tick
, now
, forcegc
, limit
;
338 uintptr released
, sumreleased
;
345 // If we go two minutes without a garbage collection, force one to run.
347 // If a span goes unused for 5 minutes after a garbage collection,
348 // we hand it back to the operating system.
350 // Make wake-up period small enough for the sampling to be correct.
357 env
= runtime_getenv("GOGCTRACE");
359 trace
= runtime_atoi(env
) > 0;
363 runtime_noteclear(¬e
);
364 runtime_entersyscall();
365 runtime_notetsleep(¬e
, tick
);
366 runtime_exitsyscall();
369 now
= runtime_nanotime();
370 if(now
- mstats
.last_gc
> forcegc
) {
374 now
= runtime_nanotime();
376 runtime_printf("scvg%d: GC forced\n", k
);
379 for(i
=0; i
< nelem(h
->free
)+1; i
++) {
380 if(i
< nelem(h
->free
))
384 if(runtime_MSpanList_IsEmpty(list
))
386 for(s
=list
->next
; s
!= list
; s
=s
->next
) {
387 if(s
->unusedsince
!= 0 && (now
- s
->unusedsince
) > limit
) {
388 released
= (s
->npages
- s
->npreleased
) << PageShift
;
389 mstats
.heap_released
+= released
;
390 sumreleased
+= released
;
391 s
->npreleased
= s
->npages
;
392 runtime_SysUnused((void*)(s
->start
<< PageShift
), s
->npages
<< PageShift
);
400 runtime_printf("scvg%d: %p MB released\n", k
, (void*)(sumreleased
>>20));
401 runtime_printf("scvg%d: inuse: %lld, idle: %lld, sys: %lld, released: %lld, consumed: %lld (MB)\n",
402 k
, (long long)(mstats
.heap_inuse
>>20), (long long)(mstats
.heap_idle
>>20), (long long)(mstats
.heap_sys
>>20),
403 (long long)(mstats
.heap_released
>>20), (long long)((mstats
.heap_sys
- mstats
.heap_released
)>>20));
408 // Initialize a new span with the given start and npages.
410 runtime_MSpan_Init(MSpan
*span
, PageID start
, uintptr npages
)
415 span
->npages
= npages
;
416 span
->freelist
= nil
;
420 span
->unusedsince
= 0;
421 span
->npreleased
= 0;
424 // Initialize an empty doubly-linked list.
426 runtime_MSpanList_Init(MSpan
*list
)
428 list
->state
= MSpanListHead
;
434 runtime_MSpanList_Remove(MSpan
*span
)
436 if(span
->prev
== nil
&& span
->next
== nil
)
438 span
->prev
->next
= span
->next
;
439 span
->next
->prev
= span
->prev
;
445 runtime_MSpanList_IsEmpty(MSpan
*list
)
447 return list
->next
== list
;
451 runtime_MSpanList_Insert(MSpan
*list
, MSpan
*span
)
453 if(span
->next
!= nil
|| span
->prev
!= nil
) {
454 // runtime_printf("failed MSpanList_Insert %p %p %p\n", span, span->next, span->prev);
455 runtime_throw("MSpanList_Insert");
457 span
->next
= list
->next
;
459 span
->next
->prev
= span
;
460 span
->prev
->next
= span
;