Re: code review 5451057: runtime: release part of unused memory to OS. (issue 5451057)

[sebastien...@gmail.com]

Functional sketch, roughly targeted toward long running (so just prevent
prominent memory waste).

Hardcoded/subjective parameters set unused memory half life to ~1mn
under steady conditions.

http://codereview.appspot.com/5451057/

[sebastien...@gmail.com]

Reviewers: golang-dev_googlegroups.com,

Message:
Hello golan...@googlegroups.com (cc: golan...@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/


Description:
runtime: release part of unused memory to OS.

Periodically browse MHeap's largest free list for droppable spans
(oldest first, 1MB min).

Please review this at http://codereview.appspot.com/5451057/

Affected files:
M src/pkg/runtime/malloc.h
M src/pkg/runtime/mheap.c
M src/pkg/runtime/proc.c


Index: src/pkg/runtime/malloc.h
===================================================================
--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -382,6 +382,7 @@
void runtime·MGetSizeClassInfo(int32 sizeclass, uintptr *size, int32
*npages, int32 *nobj);
void* runtime·MHeap_SysAlloc(MHeap *h, uintptr n);
void runtime·MHeap_MapBits(MHeap *h);
+void runtime·MHeap_Release();

void* runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32
zeroed);
int32 runtime·mlookup(void *v, byte **base, uintptr *size, MSpan **s);
Index: src/pkg/runtime/mheap.c
===================================================================
--- a/src/pkg/runtime/mheap.c
+++ b/src/pkg/runtime/mheap.c
@@ -321,6 +321,86 @@
// TODO(rsc): IncrementalScavenge() to return memory to OS.
}

+// Release (part of) unused memory to OS.
+// Goroutine created in runtime·schedinit.
+// Loop forever.
+void
+runtime·MHeap_Release()
+{
+ int64 tickPeriod = 10e9;
+ float64 cutRatio = 0.1;
+
+ MHeap *h;
+ MSpan *s, *prev;
+ PageID p;
+ uintptr target, cut, n;
+ uint64 prev_idle, prev_inuse, sz;
+
+ h = &runtime·mheap;
+ prev_inuse = prev_idle = 0;
+
+ for (;;) {
+ g->status = Gwaiting;
+ g->waitreason = "MHeap_Release pause";
+ runtime·tsleep(tickPeriod);
+
+ runtime·lock(h);
+
+ if (runtime·MSpanList_IsEmpty(&h->large)) {
+ goto NextRound;
+ }
+ // Try to not hurt transient allocations.
+ if (mstats.heap_inuse > prev_inuse) {
+ // Some more hysteresis control is needed.
+ goto NextRound;
+ }
+ target = cutRatio * (mstats.heap_idle >> PageShift); cut = 0;
+
+ // Small boost toward heap_idle trend.
+ if (mstats.heap_idle > prev_idle) {
+ target *= 2;
+ }
+ else if (mstats.heap_idle < prev_idle) {
+ target /= 2;
+ }
+
+ // Cut until target is overtaken, oldest spans first.
+ for (s = &h->large; s->next != &h->large; s = s->next) {
+ }
+ for (prev = s->prev; prev->next != &h->large && cut < target; prev =
prev->prev) {
+ s = prev->next;
+
+ // Prevent fragmentation.
+ if (s->npages < (HeapAllocChunk >> PageShift)) {
+ // Won't happen as long as (HeapAllocChunk >> PageShift) ==
MaxMHeapList
+ continue;
+ }
+ cut += s->npages;
+
+ sz = s->npages << PageShift;
+ runtime·SysFree((void*)(s->start << PageShift), sz);
+ mstats.heap_sys -= sz;
+ mstats.heap_idle -= sz;
+
+ // Make sure MHeap_FreeLocked won't coalesce with unmaped chunks.
+ p = s->start;
+ if(sizeof(void*) == 8)
+ p -= ((uintptr)h->arena_start >> PageShift);
+ for(n = 0; n < s->npages; n++)
+ h->map[p+n] = nil;
+
+ runtime·MSpanList_Remove(s);
+ runtime·FixAlloc_Free(&h->spanalloc, s);
+ mstats.mspan_inuse = h->spanalloc.inuse;
+ mstats.mspan_sys = h->spanalloc.sys;
+ }
+NextRound:
+ prev_idle = mstats.heap_idle;
+ prev_inuse = mstats.heap_inuse;
+ runtime·unlock(h);
+ }
+}
+
// Initialize a new span with the given start and npages.
void
runtime·MSpan_Init(MSpan *span, PageID start, uintptr npages)
Index: src/pkg/runtime/proc.c
===================================================================
--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -206,6 +206,8 @@

mstats.enablegc = 1;
m->nomemprof--;
+
+ runtime·newproc1((byte*)runtime·MHeap_Release, nil, 0, 0,
runtime·schedinit);
}

extern void main·init(void);

[Russ Cox]

Hi,

Thanks very much for doing this. Before I look at the code,
I'd like to talk some about the actual algorithm you are planning
to use, as per http://golang.org/doc/contribute.html#Design.

Can you summarize the algorithm in text (as opposed to code)?

Thanks.
Russ

[Sébastien Paolacci]

I'll do that for sure. That's actually what my golang-nuts post
(~"Giving back some unused memory to system" ) was meant to be
about... but it somehow diverge from my original intentions.

Thanks,
Sebastien

[dvy...@google.com]

Generally I like the design. It's nice that it's only a once per 10 sec
activity. I have only 2 high-level concerns.

1. The algo is guided by the instant heap_idle/heap_inuse values. I
think they can be quite misleading. What if the process routinely uses
1GB of memory, but at the very moment when the goroutine awakes it sees
heap_inuse=100MB (temporal load decrease + recent GC)? It will over-free
memory, something that we want to avoid at least in the first version. I
think the algo must be guided by max heap inuse during the period (or
min heap idle during period), it is more meaningful. For example, if the
process did not used more than 1GB during the whole period and we have
something on top of that, then we can free some of that excess.

2. I am not actually sure how important it is... but if it is simple to
implement and we agree that it can't hurt, it may be worth trying.
Even if there is no idle sys memory, there can be a significant amount
of non-yet-collected free memory (we just don't do GC since it become
unused). A straightforward solution is to trigger GC once per 10
seconds. However, I guess we don't want to do it. So the proposed
solution is as follows.
The decision is guided by 2 condition:
A = was there a normal GC during that 10 seconds?
B = does our release procedure triggered the last GC?
Then the algo is:
if A -> do nothing // the process seems to have everything under control
if B -> do nothing // we've already tried to do GC, and the process had
not done enough allocations since that to trigger GC
otherwise -> do GC
Humm... I am not because we don't actually know when the additional GC
worth doing (when the process is done with the memory).

http://codereview.appspot.com/5451057/

[dvy...@google.com]

Some nitpicks


http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c
File src/pkg/runtime/mheap.c (right):

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode328
src/pkg/runtime/mheap.c:328: runtime·MHeap_Release()
I think we need a better/longer name. "Release" looks like a part of
normal operation. Scavenger?

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode349
src/pkg/runtime/mheap.c:349: if (runtime·MSpanList_IsEmpty(&h->large)) {
Perhaps straight check (heap_idle < HeapAllocChunk) or some other
constant. If there is a negligible amount of memory that we can
potentially free, don't bother trying.

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode349
src/pkg/runtime/mheap.c:349: if (runtime·MSpanList_IsEmpty(&h->large)) {
Drop excessive curly brackets here and below.

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode357
src/pkg/runtime/mheap.c:357: target = cutRatio * (mstats.heap_idle >>
PageShift); cut = 0;
one statement per line please

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode357
src/pkg/runtime/mheap.c:357: target = cutRatio * (mstats.heap_idle >>
PageShift); cut = 0;
I think target can be 0, then don't bother doing anything else.

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode368
src/pkg/runtime/mheap.c:368: for (s = &h->large; s->next != &h->large; s
= s->next) {
can't we just do something along the lines of
s = h->large->prev
?

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode398
src/pkg/runtime/mheap.c:398: prev_idle = mstats.heap_idle;
identation

http://codereview.appspot.com/5451057/

[dvy...@google.com]

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c
File src/pkg/runtime/mheap.c (right):

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode344
src/pkg/runtime/mheap.c:344: g->waitreason = "MHeap_Release pause";
It is user-visible, please provide an end user understandable
description.

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode353
src/pkg/runtime/mheap.c:353: if (mstats.heap_inuse > prev_inuse) {
I think it is a way too restrictive (taking into account that the check
is executed once per 10 seconds).

http://codereview.appspot.com/5451057/diff/1002/src/pkg/runtime/mheap.c#newcode397
src/pkg/runtime/mheap.c:397: NextRound:
Perhaps a user would like to check how it works for him. What about
providing a one-line summary if GOGCTRACE>0? The summary may include the
values, how much we've scavenged or why we've scavenged nothing.

http://codereview.appspot.com/5451057/

[Sébastien Paolacci]

For cross-reference, a more literal variant is available in the thread
http://groups.google.com/group/golang-nuts/browse_thread/thread/5819498d3fb3bbb1/829dbcda0b091314
(20th msg).

[Sébastien Paolacci]

On Sat, Dec 3, 2011 at 1:21 PM, <dvy...@google.com> wrote:

> 1. The algo is guided by the instant heap_idle/heap_inuse values. I
> think they can be quite misleading. What if the process routinely uses
> 1GB of memory, but at the very moment when the goroutine awakes it sees
> heap_inuse=100MB (temporal load decrease + recent GC)? It will over-free
> memory, something that we want to avoid at least in the first version. I
> think the algo must be guided by max heap inuse during the period (or
> min heap idle during period), it is more meaningful. For example, if the
> process did not used more than 1GB during the whole period and we have
> something on top of that, then we can free some of that excess.

Yes. If unlucky, more memory than what will later be needed can be
gave-back to the OS.

On the next round however, mheap_sys will have increased because of
the newly sys-allocated blocks, we'll then know that we've freed to
much memory and won't make the mistake twice (in a row). That scheme
also covers situations where mheap_sys just keep growing, because the
overall memory need is constantly increasing, without having to pay
attention to, or rely on, mheap_idle local variations (e.g init
stages).

A high water mark on mheap_inuse would indeed bear much more precise
information. We however don't have all the room we'd like for the
exact amount of memory to be released definition (constrained by
HeapAllocChunk and mainly by what's available in &h->large), so I'm
not sure adding too much sharpness here will ultimately improve the
end result.

A kind of saturating counter could also mitigate mheap_sys' condition
correctness.

> 2. I am not actually sure how important it is... but if it is simple to
> implement and we agree that it can't hurt, it may be worth trying.
> Even if there is no idle sys memory, there can be a significant amount
> of non-yet-collected free memory (we just don't do GC since it become
> unused). A straightforward solution is to trigger GC once per 10
> seconds. However, I guess we don't want to do it. So the proposed
> solution is as follows.
> The decision is guided by 2 condition:
> A = was there a normal GC during that 10 seconds?
> B = does our release procedure triggered the last GC?
> Then the algo is:
> if A -> do nothing // the process seems to have everything under control
> if B -> do nothing // we've already tried to do GC, and the process had
> not done enough allocations since that to trigger GC
> otherwise -> do GC
> Humm... I am not because we don't actually know when the additional GC
> worth doing (when the process is done with the memory).

I really think we should remain as loosely coupled as possible from
the GC and/or other components.

My initial purpose was just to make sure that unused memory will
eventually tend to ~zero, i.e toward something that is not significant
in comparison to what the process actually needs. In that regard,
waiting few more iterations for non-yet-collected memory to become
sys-releasable is not an issue to me. But that's just my intended
use-case.

Sebastien

[sebastien...@gmail.com]

Hello golan...@googlegroups.com, r...@golang.org, dvy...@google.com
(cc: golan...@googlegroups.com),

Please take another look.

http://codereview.appspot.com/5451057/

[Sébastien Paolacci]

Hello Dmitry, thanks for the review.

> src/pkg/runtime/mheap.c:328: runtime·MHeap_Release()
> I think we need a better/longer name. "Release" looks like a part of
> normal operation. Scavenger?

Done. I have no real preference here, I tried to emphasize the
particular point of giving back memory to the OS but the dynamic
aspect was clearly missing.

> src/pkg/runtime/mheap.c:349: if (runtime·MSpanList_IsEmpty(&h->large))
> Perhaps straight check (heap_idle < HeapAllocChunk) or some other
> constant. If there is a negligible amount of memory that we can
> potentially free, don't bother trying.

Taken into consideration in the prune loop (can't drop span <
HeapAllocChunk), so I would rather postpone this kind of fast path
optim and avoid condition redundancy whenever possible, for now. I
actually remove that whole statement. One less potential trigger to
setup imho.

> src/pkg/runtime/mheap.c:349: if (runtime·MSpanList_IsEmpty(&h->large)) {
> Drop excessive curly brackets here and below.

Fixed.

> src/pkg/runtime/mheap.c:357: target = cutRatio * (mstats.heap_idle >>
> PageShift); cut = 0;
> one statement per line please

Fixed.

> src/pkg/runtime/mheap.c:357: target = cutRatio * (mstats.heap_idle >>
> PageShift); cut = 0;
> I think target can be 0, then don't bother doing anything else.

If target is zero, we shouldn't find much candidates for deletion
anyway (a bit the same to me as the above fast path).

> src/pkg/runtime/mheap.c:368: for (s = &h->large; s->next != &h->large; s
> = s->next) {
> can't we just do something along the lines of
> s = h->large->prev
> ?

You're right. I definitely missed h->large's cyclicity. Thanks.

> src/pkg/runtime/mheap.c:398: prev_idle = mstats.heap_idle;
> identation

Fixed.

> src/pkg/runtime/mheap.c:344: g->waitreason = "MHeap_Release pause";
> It is user-visible, please provide an end user understandable
> description.

I did try;), it's now "scavenger asleep". No much better idea however.

> src/pkg/runtime/mheap.c:353: if (mstats.heap_inuse > prev_inuse) {
> I think it is a way too restrictive (taking into account that the check
> is executed once per 10 seconds).

Stupid mistake, I'm sorry. The test was meant to be on mheap_sys as a
(cheap) low water mark proxy for mheap_idle. The point was to try to
mitigate transient allocations (hence the comment).
I purposely refrained myself from injecting special purpose / alien
variables into the mstats structure (among others) as to keep the
initial footprint as small as possible. That's however clearly an
option, but I'm not sure about the real impact in the end.

> src/pkg/runtime/mheap.c:397: NextRound:
> Perhaps a user would like to check how it works for him. What about
> providing a one-line summary if GOGCTRACE>0? The summary may include the
> values, how much we've scavenged or why we've scavenged nothing.

Done (more than one line however).

Sebastien

[dvy...@google.com]

http://codereview.appspot.com/5451057/diff/8/src/pkg/runtime/mheap.c
File src/pkg/runtime/mheap.c (right):

http://codereview.appspot.com/5451057/diff/8/src/pkg/runtime/mheap.c#newcode420
src/pkg/runtime/mheap.c:420: k += 1;
k++
I like k += 1 myself , but k++ seems to be a convention in the codebase

http://codereview.appspot.com/5451057/

[dvy...@google.com]

On 2011/12/04 14:01:08, Sebastien Paolacci wrote:

I still would prefer mheap_sys_max, it's just a few additional lines of
code I think it will provide much better protection against freeing what
is actually actively used by a program (I think the current algo can
easily free used memory 2 times in a row).

I see that it works poorly for computation intensive application - the
scavenger just does not have a chance to run. But I think it's a part of
a bigger problem with non-preemptiveness, and it makes a little sense to
solve it here.

I've tested it on test/bench/binary-tree.go with -n=22. And I see a lot
(dozens) of consecutive record like:

scvg22: unused: 379 of 710 MB
scvg22: target: 18 MB+
scvg22: no candidate span

The program in a sort of settled state, but the scavenger fails to
release any of that 380MB during minutes. I think we need to do
something with that.

Also I see that that boosting logic is quite unstable:

scvg28: unused: 375 of 710 MB
scvg28: target: 75 MB+
scvg28: no candidate span

scvg29: unused: 367 of 710 MB
scvg29: target: 18 MB+
scvg29: no candidate span

Basically nothing is changed in the application, but target is 4x lower.
Not sure whether we want to do something with it, perhaps it is OK as
is.

And the last concern is about huge idle spans. Consider that all idle
memory is coalesced together into a huge idle span and then the
scavenger frees it. I think it makes sense to split spans if we are
going to exceed the target significantly (like it is done in
MHeap_AllocLocked).

> My initial purpose was just to make sure that unused memory will
> eventually tend to ~zero, i.e toward something that is not significant
> in comparison to what the process actually needs. In that regard,
> waiting few more iterations for non-yet-collected memory to become
> sys-releasable is not an issue to me. But that's just my intended
> use-case.

Makes sense.

http://codereview.appspot.com/5451057/

[Russ Cox]

I was hoping for the discussion to happen in this thread.
I see now that it moved back to golang-nuts, although
there wasn't much. Sorry for not jumping in there.

I hope we can make this a little simpler, along these lines:

1. Add 'lastinuse int64' to each MSpan.
2. At the beginning of a garbage collection (not the end),
walk the span list and set m->lastinuse = now
for all the spans that are in use (not free),
where now is runtime.nanotime() from the beginning
of the garbage collection.
3. Add lastgc int64 somewhere, maybe in MHeap.
Set it to now at the beginning of the garbage collection.

Once a minute or so:

1. Run a garbage collection if there hasn't been one
in the last two minutes.

2. Walk the span list. Any span that was lastinuse
more than five minutes ago can be handed back to
the OS, but left in the list, by calling SysUnused.
Mark the span 'idle'. The next allocation from the span
or merging of the span with an adjacent span should
clear the idle flag.

Calling SysFree seems like asking for trouble.
SysUnused is just as effective and much easier.

The idea here is to wait long enough that even if we
did have to page the memory back in, it wouldn't be
a significant time cost compared to how long we held
it while idle. I get nervous when I see decisions being
made on the basis of heap size.

Does this seem reasonable, Sebastien and Dmitriy?

We will also have to update the deadlock check not to
think of the scavenger goroutine as something that
is contributing to the program execution.

Russ

[Sébastien Paolacci]

Hello Russ,

Slightly more intrusive but I'm definitely fine with the idea.

What about tagging spans with an 'unusedsince' attribute (instead of
'lastinuse'), walk mheap's freelists at the end of garbage collections
and stamp spans iif (s->state == MSpanFree && s->usedsince == 0)? That
attribute would then be reseted when spans' state change from
MSpanFree to whatever (few occurrencies iirc).

It preserves the same logic but possibly provides with a more general
span aging information. It also does not require any gc/scavanger
dynamic coupling. Whilst still being an option, the need for forcing
garbage collections (under some cicumstances) from the scavenger
vanishes, as well as few possible sampling considerations.

> Calling SysFree seems like asking for trouble.
> SysUnused is just as effective and much easier.

If it can't work with SysFree I guess we have an issue somewhere, but
SysUnused has some nice advantages.

> The idea here is to wait long enough that even if we
> did have to page the memory back in, it wouldn't be
> a significant time cost compared to how long we held
> it while idle.

In that regard 5 mn should indeed be a large enough buffer. It suits
my own use-cases anyway.

> I get nervous when I see decisions being made on
> the basis of heap size.

Possibly the best argument;)

Thanks,
Sebastien

[Sébastien Paolacci]

If I rotate my brain a little bit, I should indeed find that both
lastinuse and unusedsince schemes (begin/end of gc passes) provide
with the same pros and cons. The only small difference is possibly in
the amount of spans to be tagged (used vs unused) but that's a second
order consideration, so I'm fine there.

Sebastien

[Dmitry Vyukov]

I think both approaches will work, however the approach based on lastinuse looks better to me. It will also solve all the problem in the current implementation (not freeing small spans, freeing huge spans, guide by momentary values).

Sebastien, if you willing to implement it, it would be great.

Can the memory that is marked as unused participate in OOM score?

How will it be implemented on Windows? We may introduce SysUsed(). SysUsed() is no-op on Linux, but on Windows SysUnused/SysUsed will de-commit/commit memory (while still leaving it as reserved). It seems that the scheme provides a point where one can call SysUsed().

[Russ Cox]

On Mon, Dec 12, 2011 at 09:20, Dmitry Vyukov <dvy...@google.com> wrote:
> Can the memory that is marked as unused participate in OOM score?

I believe that only resident memory counts for OOM.
Memory that is unused is the first to go (and then
doesn't count as resident) when the OOM handler kicks in.

> How will it be implemented on Windows?

Let's get non-Windows working first and then we can
reevaluate. If we have to move to forcible eviction
that's fine but I'd like to get the unused stuff working
first.

Russ

[Sébastien Paolacci]

Hello,

I'm missing free time right now but I hope to be able to get that done
in the next few days.

I'll favor the 'unusedsince' scheme, partly because of the concerned
span list being eventually smaller, but also because tagging on a
steady/initial state looks to me like being potentially less prone to
transition corner-case later embarrassments (e.g trimmed spans).

Yes, hinting for unused memory is advantageously gratified by the OOM
(/proc/pid/oom_score, highest score killed first).

Sebastien

[Sébastien Paolacci]

#-- Sorry for the previous ill-formatted mail.

Hello Russ, Dmitry,

I've uploaded a new duration based implementation.

Most of the nasty parts come from accounting and mixed (partly
released) spans. I've added a separated entry in mstat such that
heap_idle common understanding is not altered.

Moving to a SysUsed scheme is doable, operations around `npreleased'
can serve as markers for such a modification. Spans might however have
to be forced to be homegenous when coalescing since injecting an
additional free page list in the span structure would probably not
really be a good deal.

You (more especially) want to double-check scheduler's deadlock
detection. I can prove, at best, that it works in some circumstances
but that's a bit weak for a generalization.

Cheers,
Sebastien

[Sébastien Paolacci]

2011/12/14 Sébastien Paolacci <sebastien...@gmail.com>: