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 // Page heap.
6 //
7 // See malloc.h for overview.
8 //
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.
11 //
12 // When a MSpan is allocated, state == MSpanInUse
13 // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
14
15 #include "runtime.h"
16 #include "arch.h"
17 #include "malloc.h"
18
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*);
24
25 static void
RecordSpan(void * vh,byte * p)26 RecordSpan(void *vh, byte *p)
27 {
28 MHeap *h;
29 MSpan *s;
30 MSpan **all;
31 uint32 cap;
32
33 h = vh;
34 s = (MSpan*)p;
35 if(h->nspan >= h->nspancap) {
36 cap = 64*1024/sizeof(all[0]);
37 if(cap < h->nspancap*3/2)
38 cap = h->nspancap*3/2;
39 all = (MSpan**)runtime_SysAlloc(cap*sizeof(all[0]));
40 if(all == nil)
41 runtime_throw("runtime: cannot allocate memory");
42 if(h->allspans) {
43 runtime_memmove(all, h->allspans, h->nspancap*sizeof(all[0]));
44 runtime_SysFree(h->allspans, h->nspancap*sizeof(all[0]));
45 }
46 h->allspans = all;
47 h->nspancap = cap;
48 }
49 h->allspans[h->nspan++] = s;
50 }
51
52 // Initialize the heap; fetch memory using alloc.
53 void
runtime_MHeap_Init(MHeap * h,void * (* alloc)(uintptr))54 runtime_MHeap_Init(MHeap *h, void *(*alloc)(uintptr))
55 {
56 uint32 i;
57
58 runtime_FixAlloc_Init(&h->spanalloc, sizeof(MSpan), alloc, RecordSpan, h);
59 runtime_FixAlloc_Init(&h->cachealloc, sizeof(MCache), alloc, nil, nil);
60 // h->mapcache needs no init
61 for(i=0; i<nelem(h->free); i++)
62 runtime_MSpanList_Init(&h->free[i]);
63 runtime_MSpanList_Init(&h->large);
64 for(i=0; i<nelem(h->central); i++)
65 runtime_MCentral_Init(&h->central[i], i);
66 }
67
68 // Allocate a new span of npage pages from the heap
69 // and record its size class in the HeapMap and HeapMapCache.
70 MSpan*
runtime_MHeap_Alloc(MHeap * h,uintptr npage,int32 sizeclass,int32 acct,int32 zeroed)71 runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct, int32 zeroed)
72 {
73 MSpan *s;
74
75 runtime_lock(h);
76 runtime_purgecachedstats(runtime_m()->mcache);
77 s = MHeap_AllocLocked(h, npage, sizeclass);
78 if(s != nil) {
79 mstats.heap_inuse += npage<<PageShift;
80 if(acct) {
81 mstats.heap_objects++;
82 mstats.heap_alloc += npage<<PageShift;
83 }
84 }
85 runtime_unlock(h);
86 if(s != nil && *(uintptr*)(s->start<<PageShift) != 0 && zeroed)
87 runtime_memclr((byte*)(s->start<<PageShift), s->npages<<PageShift);
88 return s;
89 }
90
91 static MSpan*
MHeap_AllocLocked(MHeap * h,uintptr npage,int32 sizeclass)92 MHeap_AllocLocked(MHeap *h, uintptr npage, int32 sizeclass)
93 {
94 uintptr n;
95 MSpan *s, *t;
96 PageID p;
97
98 // Try in fixed-size lists up to max.
99 for(n=npage; n < nelem(h->free); n++) {
100 if(!runtime_MSpanList_IsEmpty(&h->free[n])) {
101 s = h->free[n].next;
102 goto HaveSpan;
103 }
104 }
105
106 // Best fit in list of large spans.
107 if((s = MHeap_AllocLarge(h, npage)) == nil) {
108 if(!MHeap_Grow(h, npage))
109 return nil;
110 if((s = MHeap_AllocLarge(h, npage)) == nil)
111 return nil;
112 }
113
114 HaveSpan:
115 // Mark span in use.
116 if(s->state != MSpanFree)
117 runtime_throw("MHeap_AllocLocked - MSpan not free");
118 if(s->npages < npage)
119 runtime_throw("MHeap_AllocLocked - bad npages");
120 runtime_MSpanList_Remove(s);
121 s->state = MSpanInUse;
122 mstats.heap_idle -= s->npages<<PageShift;
123 mstats.heap_released -= s->npreleased<<PageShift;
124 if(s->npreleased > 0) {
125 // We have called runtime_SysUnused with these pages, and on
126 // Unix systems it called madvise. At this point at least
127 // some BSD-based kernels will return these pages either as
128 // zeros or with the old data. For our caller, the first word
129 // in the page indicates whether the span contains zeros or
130 // not (this word was set when the span was freed by
131 // MCentral_Free or runtime_MCentral_FreeSpan). If the first
132 // page in the span is returned as zeros, and some subsequent
133 // page is returned with the old data, then we will be
134 // returning a span that is assumed to be all zeros, but the
135 // actual data will not be all zeros. Avoid that problem by
136 // explicitly marking the span as not being zeroed, just in
137 // case. The beadbead constant we use here means nothing, it
138 // is just a unique constant not seen elsewhere in the
139 // runtime, as a clue in case it turns up unexpectedly in
140 // memory or in a stack trace.
141 *(uintptr*)(s->start<<PageShift) = (uintptr)0xbeadbeadbeadbeadULL;
142 }
143 s->npreleased = 0;
144
145 if(s->npages > npage) {
146 // Trim extra and put it back in the heap.
147 t = runtime_FixAlloc_Alloc(&h->spanalloc);
148 mstats.mspan_inuse = h->spanalloc.inuse;
149 mstats.mspan_sys = h->spanalloc.sys;
150 runtime_MSpan_Init(t, s->start + npage, s->npages - npage);
151 s->npages = npage;
152 p = t->start;
153 p -= ((uintptr)h->arena_start>>PageShift);
154 if(p > 0)
155 h->map[p-1] = s;
156 h->map[p] = t;
157 h->map[p+t->npages-1] = t;
158 *(uintptr*)(t->start<<PageShift) = *(uintptr*)(s->start<<PageShift); // copy "needs zeroing" mark
159 t->state = MSpanInUse;
160 MHeap_FreeLocked(h, t);
161 t->unusedsince = s->unusedsince; // preserve age
162 }
163 s->unusedsince = 0;
164
165 // Record span info, because gc needs to be
166 // able to map interior pointer to containing span.
167 s->sizeclass = sizeclass;
168 s->elemsize = (sizeclass==0 ? s->npages<<PageShift : (uintptr)runtime_class_to_size[sizeclass]);
169 s->types.compression = MTypes_Empty;
170 p = s->start;
171 p -= ((uintptr)h->arena_start>>PageShift);
172 for(n=0; n<npage; n++)
173 h->map[p+n] = s;
174 return s;
175 }
176
177 // Allocate a span of exactly npage pages from the list of large spans.
178 static MSpan*
MHeap_AllocLarge(MHeap * h,uintptr npage)179 MHeap_AllocLarge(MHeap *h, uintptr npage)
180 {
181 return BestFit(&h->large, npage, nil);
182 }
183
184 // Search list for smallest span with >= npage pages.
185 // If there are multiple smallest spans, take the one
186 // with the earliest starting address.
187 static MSpan*
BestFit(MSpan * list,uintptr npage,MSpan * best)188 BestFit(MSpan *list, uintptr npage, MSpan *best)
189 {
190 MSpan *s;
191
192 for(s=list->next; s != list; s=s->next) {
193 if(s->npages < npage)
194 continue;
195 if(best == nil
196 || s->npages < best->npages
197 || (s->npages == best->npages && s->start < best->start))
198 best = s;
199 }
200 return best;
201 }
202
203 // Try to add at least npage pages of memory to the heap,
204 // returning whether it worked.
205 static bool
MHeap_Grow(MHeap * h,uintptr npage)206 MHeap_Grow(MHeap *h, uintptr npage)
207 {
208 uintptr ask;
209 void *v;
210 MSpan *s;
211 PageID p;
212
213 // Ask for a big chunk, to reduce the number of mappings
214 // the operating system needs to track; also amortizes
215 // the overhead of an operating system mapping.
216 // Allocate a multiple of 64kB (16 pages).
217 npage = (npage+15)&~15;
218 ask = npage<<PageShift;
219 if(ask < HeapAllocChunk)
220 ask = HeapAllocChunk;
221
222 v = runtime_MHeap_SysAlloc(h, ask);
223 if(v == nil) {
224 if(ask > (npage<<PageShift)) {
225 ask = npage<<PageShift;
226 v = runtime_MHeap_SysAlloc(h, ask);
227 }
228 if(v == nil) {
229 runtime_printf("runtime: out of memory: cannot allocate %D-byte block (%D in use)\n", (uint64)ask, mstats.heap_sys);
230 return false;
231 }
232 }
233 mstats.heap_sys += ask;
234
235 // Create a fake "in use" span and free it, so that the
236 // right coalescing happens.
237 s = runtime_FixAlloc_Alloc(&h->spanalloc);
238 mstats.mspan_inuse = h->spanalloc.inuse;
239 mstats.mspan_sys = h->spanalloc.sys;
240 runtime_MSpan_Init(s, (uintptr)v>>PageShift, ask>>PageShift);
241 p = s->start;
242 p -= ((uintptr)h->arena_start>>PageShift);
243 h->map[p] = s;
244 h->map[p + s->npages - 1] = s;
245 s->state = MSpanInUse;
246 MHeap_FreeLocked(h, s);
247 return true;
248 }
249
250 // Look up the span at the given address.
251 // Address is guaranteed to be in map
252 // and is guaranteed to be start or end of span.
253 MSpan*
runtime_MHeap_Lookup(MHeap * h,void * v)254 runtime_MHeap_Lookup(MHeap *h, void *v)
255 {
256 uintptr p;
257
258 p = (uintptr)v;
259 p -= (uintptr)h->arena_start;
260 return h->map[p >> PageShift];
261 }
262
263 // Look up the span at the given address.
264 // Address is *not* guaranteed to be in map
265 // and may be anywhere in the span.
266 // Map entries for the middle of a span are only
267 // valid for allocated spans. Free spans may have
268 // other garbage in their middles, so we have to
269 // check for that.
270 MSpan*
runtime_MHeap_LookupMaybe(MHeap * h,void * v)271 runtime_MHeap_LookupMaybe(MHeap *h, void *v)
272 {
273 MSpan *s;
274 PageID p, q;
275
276 if((byte*)v < h->arena_start || (byte*)v >= h->arena_used)
277 return nil;
278 p = (uintptr)v>>PageShift;
279 q = p;
280 q -= (uintptr)h->arena_start >> PageShift;
281 s = h->map[q];
282 if(s == nil || p < s->start || p - s->start >= s->npages)
283 return nil;
284 if(s->state != MSpanInUse)
285 return nil;
286 return s;
287 }
288
289 // Free the span back into the heap.
290 void
runtime_MHeap_Free(MHeap * h,MSpan * s,int32 acct)291 runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct)
292 {
293 runtime_lock(h);
294 runtime_purgecachedstats(runtime_m()->mcache);
295 mstats.heap_inuse -= s->npages<<PageShift;
296 if(acct) {
297 mstats.heap_alloc -= s->npages<<PageShift;
298 mstats.heap_objects--;
299 }
300 MHeap_FreeLocked(h, s);
301 runtime_unlock(h);
302 }
303
304 static void
MHeap_FreeLocked(MHeap * h,MSpan * s)305 MHeap_FreeLocked(MHeap *h, MSpan *s)
306 {
307 uintptr *sp, *tp;
308 MSpan *t;
309 PageID p;
310
311 if(s->types.sysalloc)
312 runtime_settype_sysfree(s);
313 s->types.compression = MTypes_Empty;
314
315 if(s->state != MSpanInUse || s->ref != 0) {
316 runtime_printf("MHeap_FreeLocked - span %p ptr %p state %d ref %d\n", s, s->start<<PageShift, s->state, s->ref);
317 runtime_throw("MHeap_FreeLocked - invalid free");
318 }
319 mstats.heap_idle += s->npages<<PageShift;
320 s->state = MSpanFree;
321 runtime_MSpanList_Remove(s);
322 sp = (uintptr*)(s->start<<PageShift);
323 // Stamp newly unused spans. The scavenger will use that
324 // info to potentially give back some pages to the OS.
325 s->unusedsince = runtime_nanotime();
326 s->npreleased = 0;
327
328 // Coalesce with earlier, later spans.
329 p = s->start;
330 p -= (uintptr)h->arena_start >> PageShift;
331 if(p > 0 && (t = h->map[p-1]) != nil && t->state != MSpanInUse) {
332 tp = (uintptr*)(t->start<<PageShift);
333 *tp |= *sp; // propagate "needs zeroing" mark
334 s->start = t->start;
335 s->npages += t->npages;
336 s->npreleased = t->npreleased; // absorb released pages
337 p -= t->npages;
338 h->map[p] = s;
339 runtime_MSpanList_Remove(t);
340 t->state = MSpanDead;
341 runtime_FixAlloc_Free(&h->spanalloc, t);
342 mstats.mspan_inuse = h->spanalloc.inuse;
343 mstats.mspan_sys = h->spanalloc.sys;
344 }
345 if(p+s->npages < nelem(h->map) && (t = h->map[p+s->npages]) != nil && t->state != MSpanInUse) {
346 tp = (uintptr*)(t->start<<PageShift);
347 *sp |= *tp; // propagate "needs zeroing" mark
348 s->npages += t->npages;
349 s->npreleased += t->npreleased;
350 h->map[p + s->npages - 1] = s;
351 runtime_MSpanList_Remove(t);
352 t->state = MSpanDead;
353 runtime_FixAlloc_Free(&h->spanalloc, t);
354 mstats.mspan_inuse = h->spanalloc.inuse;
355 mstats.mspan_sys = h->spanalloc.sys;
356 }
357
358 // Insert s into appropriate list.
359 if(s->npages < nelem(h->free))
360 runtime_MSpanList_Insert(&h->free[s->npages], s);
361 else
362 runtime_MSpanList_Insert(&h->large, s);
363 }
364
365 static void
forcegchelper(void * vnote)366 forcegchelper(void *vnote)
367 {
368 Note *note = (Note*)vnote;
369
370 runtime_gc(1);
371 runtime_notewakeup(note);
372 }
373
374 static uintptr
scavengelist(MSpan * list,uint64 now,uint64 limit)375 scavengelist(MSpan *list, uint64 now, uint64 limit)
376 {
377 uintptr released, sumreleased;
378 MSpan *s;
379
380 if(runtime_MSpanList_IsEmpty(list))
381 return 0;
382
383 sumreleased = 0;
384 for(s=list->next; s != list; s=s->next) {
385 if((now - s->unusedsince) > limit) {
386 released = (s->npages - s->npreleased) << PageShift;
387 mstats.heap_released += released;
388 sumreleased += released;
389 s->npreleased = s->npages;
390 runtime_SysUnused((void*)(s->start << PageShift), s->npages << PageShift);
391 }
392 }
393 return sumreleased;
394 }
395
396 static uintptr
scavenge(uint64 now,uint64 limit)397 scavenge(uint64 now, uint64 limit)
398 {
399 uint32 i;
400 uintptr sumreleased;
401 MHeap *h;
402
403 h = runtime_mheap;
404 sumreleased = 0;
405 for(i=0; i < nelem(h->free); i++)
406 sumreleased += scavengelist(&h->free[i], now, limit);
407 sumreleased += scavengelist(&h->large, now, limit);
408 return sumreleased;
409 }
410
411 // Release (part of) unused memory to OS.
412 // Goroutine created at startup.
413 // Loop forever.
414 void
runtime_MHeap_Scavenger(void * dummy)415 runtime_MHeap_Scavenger(void* dummy)
416 {
417 G *g;
418 MHeap *h;
419 uint64 tick, now, forcegc, limit;
420 uint32 k;
421 uintptr sumreleased;
422 const byte *env;
423 bool trace;
424 Note note, *notep;
425
426 USED(dummy);
427
428 g = runtime_g();
429 g->issystem = true;
430 g->isbackground = true;
431
432 // If we go two minutes without a garbage collection, force one to run.
433 forcegc = 2*60*1e9;
434 // If a span goes unused for 5 minutes after a garbage collection,
435 // we hand it back to the operating system.
436 limit = 5*60*1e9;
437 // Make wake-up period small enough for the sampling to be correct.
438 if(forcegc < limit)
439 tick = forcegc/2;
440 else
441 tick = limit/2;
442
443 trace = false;
444 env = runtime_getenv("GOGCTRACE");
445 if(env != nil)
446 trace = runtime_atoi(env) > 0;
447
448 h = runtime_mheap;
449 for(k=0;; k++) {
450 runtime_noteclear(¬e);
451 runtime_entersyscallblock();
452 runtime_notetsleep(¬e, tick);
453 runtime_exitsyscall();
454
455 runtime_lock(h);
456 now = runtime_nanotime();
457 if(now - mstats.last_gc > forcegc) {
458 runtime_unlock(h);
459 // The scavenger can not block other goroutines,
460 // otherwise deadlock detector can fire spuriously.
461 // GC blocks other goroutines via the runtime_worldsema.
462 runtime_noteclear(¬e);
463 notep = ¬e;
464 __go_go(forcegchelper, (void*)notep);
465 runtime_entersyscallblock();
466 runtime_notesleep(¬e);
467 runtime_exitsyscall();
468 if(trace)
469 runtime_printf("scvg%d: GC forced\n", k);
470 runtime_lock(h);
471 now = runtime_nanotime();
472 }
473 sumreleased = scavenge(now, limit);
474 runtime_unlock(h);
475
476 if(trace) {
477 if(sumreleased > 0)
478 runtime_printf("scvg%d: %p MB released\n", k, sumreleased>>20);
479 runtime_printf("scvg%d: inuse: %D, idle: %D, sys: %D, released: %D, consumed: %D (MB)\n",
480 k, mstats.heap_inuse>>20, mstats.heap_idle>>20, mstats.heap_sys>>20,
481 mstats.heap_released>>20, (mstats.heap_sys - mstats.heap_released)>>20);
482 }
483 }
484 }
485
486 void runtime_debug_freeOSMemory(void) __asm__("runtime_debug.freeOSMemory");
487
488 void
runtime_debug_freeOSMemory(void)489 runtime_debug_freeOSMemory(void)
490 {
491 runtime_gc(1);
492 runtime_lock(runtime_mheap);
493 scavenge(~(uintptr)0, 0);
494 runtime_unlock(runtime_mheap);
495 }
496
497 // Initialize a new span with the given start and npages.
498 void
runtime_MSpan_Init(MSpan * span,PageID start,uintptr npages)499 runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages)
500 {
501 span->next = nil;
502 span->prev = nil;
503 span->start = start;
504 span->npages = npages;
505 span->freelist = nil;
506 span->ref = 0;
507 span->sizeclass = 0;
508 span->elemsize = 0;
509 span->state = 0;
510 span->unusedsince = 0;
511 span->npreleased = 0;
512 span->types.compression = MTypes_Empty;
513 }
514
515 // Initialize an empty doubly-linked list.
516 void
runtime_MSpanList_Init(MSpan * list)517 runtime_MSpanList_Init(MSpan *list)
518 {
519 list->state = MSpanListHead;
520 list->next = list;
521 list->prev = list;
522 }
523
524 void
runtime_MSpanList_Remove(MSpan * span)525 runtime_MSpanList_Remove(MSpan *span)
526 {
527 if(span->prev == nil && span->next == nil)
528 return;
529 span->prev->next = span->next;
530 span->next->prev = span->prev;
531 span->prev = nil;
532 span->next = nil;
533 }
534
535 bool
runtime_MSpanList_IsEmpty(MSpan * list)536 runtime_MSpanList_IsEmpty(MSpan *list)
537 {
538 return list->next == list;
539 }
540
541 void
runtime_MSpanList_Insert(MSpan * list,MSpan * span)542 runtime_MSpanList_Insert(MSpan *list, MSpan *span)
543 {
544 if(span->next != nil || span->prev != nil) {
545 runtime_printf("failed MSpanList_Insert %p %p %p\n", span, span->next, span->prev);
546 runtime_throw("MSpanList_Insert");
547 }
548 span->next = list->next;
549 span->prev = list;
550 span->next->prev = span;
551 span->prev->next = span;
552 }
553
554
555