code review 5279048: runtime: faster and more scalable GC

src/pkg/runtime/mheap.c

 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Page heap.
 //
 // See malloc.h for overview.
 //
 // When a MSpan is in the heap free list, state == MSpanFree
 // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span.
 //
 // When a MSpan is allocated, state == MSpanInUse
 // and heapmap(i) == span for all s->start <= i < s->start+s->npages.
 
 #include "runtime.h"
-#include "arch.h"
+#include "arch_GOARCH.h"
 #include "malloc.h"
 
 static MSpan *MHeap_AllocLocked(MHeap*, uintptr, int32);
 static bool MHeap_Grow(MHeap*, uintptr);
 static void MHeap_FreeLocked(MHeap*, MSpan*);
 static MSpan *MHeap_AllocLarge(MHeap*, uintptr);
 static MSpan *BestFit(MSpan*, uintptr, MSpan*);
 
 static void
 RecordSpan(void *vh, byte *p)
 {
         MHeap *h;
         MSpan *s;
-
+        MSpan **all;
+        uintptr cap;
+ ·······
         h = vh;
         s = (MSpan*)p;
-        //s->allnext = h->allspans;
-        //h->allspans = s;
-        if(h->nspan == nelem(h->allspans))
-                runtime·throw("span overflow");
-        h->allspans[h->nspan] = s;
-        h->nspan++;
+        if(h->nspan >= h->nspancap) {
+                cap = 64*1024/sizeof(MSpan*);
+                if(cap < h->nspancap*3/2)
+                        cap = h->nspancap*3/2;
+                all = (MSpan**)runtime·SysAlloc(cap*sizeof(MSpan*));
+                if(h->allspans) {
+                        runtime·memmove(all, h->allspans, h->nspancap*sizeof(MSpan*));
+                        runtime·SysFree(h->allspans, h->nspancap*sizeof(MSpan*));
+                }
+                h->allspans = all;
+                h->nspancap = cap;
+        }
+        h->allspans[h->nspan++] = s;
 }
 
 // Initialize the heap; fetch memory using alloc.
 void
 runtime·MHeap_Init(MHeap *h, void *(*alloc)(uintptr))
 {
         uint32 i;
 
         runtime·FixAlloc_Init(&h->spanalloc, sizeof(MSpan), alloc, RecordSpan, h);
         runtime·FixAlloc_Init(&h->cachealloc, sizeof(MCache), alloc, nil, nil);
@@ skipping 51 matching lines @@
 
 HaveSpan:
         // Mark span in use.
         if(s->state != MSpanFree)
                 runtime·throw("MHeap_AllocLocked - MSpan not free");
         if(s->npages < npage)
                 runtime·throw("MHeap_AllocLocked - bad npages");
         runtime·MSpanList_Remove(s);
         s->state = MSpanInUse;
         mstats.heap_idle -= s->npages<<PageShift;
+        mstats.heap_released -= s->npreleased<<PageShift;
+        s->npreleased = 0;
 
         if(s->npages > npage) {
                 // Trim extra and put it back in the heap.
                 t = runtime·FixAlloc_Alloc(&h->spanalloc);
                 mstats.mspan_inuse = h->spanalloc.inuse;
                 mstats.mspan_sys = h->spanalloc.sys;
                 runtime·MSpan_Init(t, s->start + npage, s->npages - npage);
                 s->npages = npage;
                 p = t->start;
                 if(sizeof(void*) == 8)
@@ skipping 157 matching lines @@
         uintptr *sp, *tp;
         MSpan *t;
         PageID p;
 
         if(s->state != MSpanInUse || s->ref != 0) {
                 runtime·printf("MHeap_FreeLocked - span %p ptr %p state %d ref %d\n", s, s->start<<PageShift, s->state, s->ref);
                 runtime·throw("MHeap_FreeLocked - invalid free");
         }
         mstats.heap_idle += s->npages<<PageShift;
         s->state = MSpanFree;
+        s->unusedsince = 0;
+        s->npreleased = 0;
         runtime·MSpanList_Remove(s);
         sp = (uintptr*)(s->start<<PageShift);
 
         // Coalesce with earlier, later spans.
         p = s->start;
         if(sizeof(void*) == 8)
                 p -= (uintptr)h->arena_start >> PageShift;
         if(p > 0 && (t = h->map[p-1]) != nil && t->state != MSpanInUse) {
                 tp = (uintptr*)(t->start<<PageShift);
                 *tp |= *sp;     // propagate "needs zeroing" mark
                 s->start = t->start;
                 s->npages += t->npages;
+                s->npreleased = t->npreleased; // absorb released pages
                 p -= t->npages;
                 h->map[p] = s;
                 runtime·MSpanList_Remove(t);
                 t->state = MSpanDead;
                 runtime·FixAlloc_Free(&h->spanalloc, t);
                 mstats.mspan_inuse = h->spanalloc.inuse;
                 mstats.mspan_sys = h->spanalloc.sys;
         }
         if(p+s->npages < nelem(h->map) && (t = h->map[p+s->npages]) != nil && t->state != MSpanInUse) {
                 tp = (uintptr*)(t->start<<PageShift);
                 *sp |= *tp;     // propagate "needs zeroing" mark
                 s->npages += t->npages;
+                s->npreleased += t->npreleased;
                 h->map[p + s->npages - 1] = s;
                 runtime·MSpanList_Remove(t);
                 t->state = MSpanDead;
                 runtime·FixAlloc_Free(&h->spanalloc, t);
                 mstats.mspan_inuse = h->spanalloc.inuse;
                 mstats.mspan_sys = h->spanalloc.sys;
         }
 
         // Insert s into appropriate list.
         if(s->npages < nelem(h->free))
                 runtime·MSpanList_Insert(&h->free[s->npages], s);
         else
                 runtime·MSpanList_Insert(&h->large, s);
-
-        // TODO(rsc): IncrementalScavenge() to return memory to OS.
+}
+
+// Release (part of) unused memory to OS.
+// Goroutine created at startup.
+// Loop forever.
+void
+runtime·MHeap_Scavenger(void)
+{
+        MHeap *h;
+        MSpan *s, *list;
+        uint64 tick, now, forcegc, limit;
+        uint32 k, i;
+        uintptr released, sumreleased;
+        byte *env;
+        bool trace;
+        Note note;
+
+        // If we go two minutes without a garbage collection, force one to run.
+        forcegc = 2*60*1e9;
+        // If a span goes unused for 5 minutes after a garbage collection,
+        // we hand it back to the operating system.
+        limit = 5*60*1e9;
+        // Make wake-up period small enough for the sampling to be correct.
+        if(forcegc < limit)
+                tick = forcegc/2;
+        else
+                tick = limit/2;
+
+        trace = false;
+        env = runtime·getenv("GOGCTRACE");
+        if(env != nil)
+                trace = runtime·atoi(env) > 0;
+
+        h = &runtime·mheap;
+        for(k=0;; k++) {
+                runtime·noteclear(&note);
+                runtime·entersyscall();
+                runtime·notetsleep(&note, tick);
+                runtime·exitsyscall();
+
+                runtime·lock(h);
+                now = runtime·nanotime();
+                if(now - mstats.last_gc > forcegc) {
+                        runtime·unlock(h);
+                        runtime·gc(1);
+                        runtime·lock(h);
+                        now = runtime·nanotime();
+                        if (trace)
+                                runtime·printf("scvg%d: GC forced\n", k);
+                }
+                sumreleased = 0;
+                for(i=0; i < nelem(h->free)+1; i++) {
+                        if(i < nelem(h->free))
+                                list = &h->free[i];
+                        else
+                                list = &h->large;
+                        if(runtime·MSpanList_IsEmpty(list))
+                                continue;
+                        for(s=list->next; s != list; s=s->next) {
+                                if(s->unusedsince != 0 && (now - s->unusedsince) > limit) {
+                                        released = (s->npages - s->npreleased) << PageShift;
+                                        mstats.heap_released += released;
+                                        sumreleased += released;
+                                        s->npreleased = s->npages;
+                                        runtime·SysUnused((void*)(s->start << PageShift), s->npages << PageShift);
+                                }
+                        }
+                }
+                runtime·unlock(h);
+
+                if(trace) {
+                        if(sumreleased > 0)
+                                runtime·printf("scvg%d: %p MB released\n", k, sumreleased>>20);
+                        runtime·printf("scvg%d: inuse: %D, idle: %D, sys: %D, released: %D, consumed: %D (MB)\n",
+                                k, mstats.heap_inuse>>20, mstats.heap_idle>>20, mstats.heap_sys>>20,
+                                mstats.heap_released>>20, (mstats.heap_sys - mstats.heap_released)>>20);
+                }
+        }
 }
 
 // Initialize a new span with the given start and npages.
 void
 runtime·MSpan_Init(MSpan *span, PageID start, uintptr npages)
 {
         span->next = nil;
         span->prev = nil;
         span->start = start;
         span->npages = npages;
         span->freelist = nil;
         span->ref = 0;
         span->sizeclass = 0;
         span->state = 0;
+        span->unusedsince = 0;
+        span->npreleased = 0;
 }
 
 // Initialize an empty doubly-linked list.
 void
 runtime·MSpanList_Init(MSpan *list)
 {
         list->state = MSpanListHead;
         list->next = list;
         list->prev = list;
 }
@@ skipping 22 matching lines @@
                 runtime·printf("failed MSpanList_Insert %p %p %p\n", span, span->next, span->prev);
                 runtime·throw("MSpanList_Insert");
         }
         span->next = list->next;
         span->prev = list;
         span->next->prev = span;
         span->prev->next = span;
 }