code review 5451057: runtime: release unused memory to the OS.

runtime: release unused memory to the OS.

Periodically browse MHeap's freelists for long unused spans and release them if any.

Current hardcoded settings:
        - GC is forced if none occured over the last 2 minutes.
        - spans are handed back after 5 minutes of uselessness.

SysUnused (for Unix) is a wrapper on madvise MADV_DONTNEED on Linux and MADV_FREE on BSDs.

[Sebastien Paolacci, 2011-11-30 21:31:22]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

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

[Sebastien Paolacci, 2011-11-30 21:42:57]

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.

[rsc, 2011-12-01 00:04:45]

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

[Sebastien Paolacci, 2011-12-01 13:02:51]

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

On Thu, Dec 1, 2011 at 1:04 AM, Russ Cox <rsc@golang.org> wrote:
> 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

[dvyukov, 2011-12-03 12:21:27]

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).

[dvyukov, 2011-12-03 12:38:09]

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#newco...
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#newco...
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#newco...
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#newco...
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#newco...
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#newco...
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#newco...
src/pkg/runtime/mheap.c:398: prev_idle = mstats.heap_idle;
identation

[dvyukov, 2011-12-03 14:20:43]

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#newco...
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#newco...
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#newco...
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.

[Sebastien Paolacci, 2011-12-04 13:07:25]

Hello golang-dev@googlegroups.com, rsc@golang.org, dvyukov@google.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[Sebastien Paolacci, 2011-12-04 13:12:14]

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

On Sat, Dec 3, 2011 at 3:20 PM,  <dvyukov@google.com> wrote:
>
> 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#newco...
> 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#newco...
> 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#newco...
> 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/

[Sebastien Paolacci, 2011-12-04 13:14:55]

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

[Sebastien Paolacci, 2011-12-04 14:01:08]

On Sat, Dec 3, 2011 at 1:21 PM,  <dvyukov@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

[dvyukov, 2011-12-07 10:22:13]

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

[dvyukov, 2011-12-07 10:39:55]

On 2011/12/04 14:01:08, Sebastien Paolacci wrote:
> On Sat, Dec 3, 2011 at 1:21 PM,  <mailto:dvyukov@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.

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.

[rsc, 2011-12-07 22:43:09]

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

[Sebastien Paolacci, 2011-12-08 20:56:35]

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

[Sebastien Paolacci, 2011-12-11 22:36:48]

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

[dvyukov, 2011-12-12 14:20:27]

On Thu, Dec 8, 2011 at 2:43 AM, Russ Cox <rsc@golang.org> wrote:

> 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?
>
>
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().

[rsc, 2011-12-12 21:51:04]

On Mon, Dec 12, 2011 at 09:20, Dmitry Vyukov <dvyukov@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

[Sebastien Paolacci, 2011-12-14 13:13:30]

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

[Sebastien Paolacci, 2011-12-19 13:01:16]

Hello golang-dev@googlegroups.com, rsc@golang.org, dvyukov@google.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[Sebastien Paolacci, 2011-12-19 13:03:24]

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
2011/12/14 Sébastien Paolacci <sebastien.paolacci@gmail.com>:
> 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

[Sebastien Paolacci, 2011-12-19 13:10:59]

#-- 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

[dvyukov, 2011-12-22 12:50:36]

Please run all the tests with various values of GOMAXPROCS:
GOMAXPROCS=N ./run.bach --no-rebuild

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/malloc.h
File src/pkg/runtime/malloc.h (right):

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:305: MSpanIdle,
Do we really need a new state? npreleased seems to be enough, especially taking
into account that there can be partially released blocks in both MSpanFree and
MSpanIdle states depending on how coalescing happens...

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

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:1035: for(i=0; i < nelem(h->free)+1; i++) {
Perhaps it's better to move this to sweep(), it already iterates over all spans
and check their states. I've seen as much as 100k spans in
test/bench/garbage/parser.go, so just iterating over them can take some time.

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

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:106: mstats.heap_released -= s->npreleased<<PageShift;
zeroize s->npreleased plz

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

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:168: G *scvg;
static

[dvyukov, 2011-12-22 12:52:06]

On 2011/12/19 13:10:59, Sebastien Paolacci wrote:
> #-- 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.

For now I may only conclude that it may work in some circumstances :)

[dvyukov, 2011-12-22 12:55:39]

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

http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:563: if (gp->goid == scvg->goid && runtime·sched.gwait ==
0 && runtime·sched.grunning == 0)
Does it detect deadlocks in trivial cases?
I need to look more into this, it seems that now we always have at least one
either running or waiting goroutine - it's either scavenger or timer
goroutine... at least one of them is always runnable... what am I missing?

[rsc, 2011-12-22 20:23:31]

On Thu, Dec 22, 2011 at 07:55,  <dvyukov@google.com> wrote:
> I need to look more into this, it seems that now we always have at least
> one either running or waiting goroutine - it's either scavenger or timer
> goroutine... at least one of them is always runnable... what am I
> missing?

This is definitely a concern.

[Sebastien Paolacci, 2011-12-30 15:36:51]

On Thu, Dec 22, 2011 at 1:50 PM,  <dvyukov@google.com> wrote:
> Please run all the tests with various values of GOMAXPROCS:
> GOMAXPROCS=N ./run.bach --no-rebuild
Checked for N in [1..8], they all pass.

>
http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/malloc.h#new...
> src/pkg/runtime/malloc.h:305: MSpanIdle,
> Do we really need a new state? npreleased seems to be enough, especially
> taking into account that there can be partially released blocks in both
> MSpanFree and MSpanIdle states depending on how coalescing happens...
You're right, there's some redundancy here. MSpanIdle makes sense in a
Unused/Used scheme, npreleased in an Unused-only approach. I've
dropped MSpanIdle.

>
http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/mgc0.c#newco...
> src/pkg/runtime/mgc0.c:1035: for(i=0; i < nelem(h->free)+1; i++) {
> Perhaps it's better to move this to sweep(), it already iterates over
> all spans and check their states. I've seen as much as 100k spans in
> test/bench/garbage/parser.go, so just iterating over them can take some
> time.
Moved.

>
http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:106: mstats.heap_released -=
> s->npreleased<<PageShift;
> zeroize s->npreleased plz
Added, not sure however how much you consider it as been a guard (zero
is a valid value).
I've kept the {unsedsince, npreleased} pair zeroing in MHeapFreeLocked.

>
http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/proc.c#newco...
> src/pkg/runtime/proc.c:168: G *scvg;
> static
Fixed.

>
http://codereview.appspot.com/5451057/diff/14001/src/pkg/runtime/proc.c#newco...
> src/pkg/runtime/proc.c:563: if (gp->goid == scvg->goid &&
> runtime·sched.gwait == 0 && runtime·sched.grunning == 0)
> Does it detect deadlocks in trivial cases?
Yes.
{
    go func() {
        time.AfterFunc(5e9, func() { println("timer stopped") })
    }()
    c := make(chan bool)
    c <- false
}
But it may need up to GOSCVGPERIOD to sort out a simple dummy steady
situation like
{
    c := make(chan bool)
    c <- false
}
or
{
    var lock sync.Mutex
    lock.Lock()
    lock.Lock()
}
So there's still some significant issues here.

> I need to look more into this, it seems that now we always have at least
> one either running or waiting goroutine - it's either scavenger or timer
> goroutine... at least one of them is always runnable... what am I
> missing?
That's also my understaning. The issue (to me) is however to catch the
right transition (`haveg()' does not break the global queue loop so
easily iirc). In that regard, I'm not sure having the scavenger coming
along on top of timer's proc is really helpful. I'll give a try to a
more standalone note-based version, it may help by sorting things out.

Sebastien

[Sebastien Paolacci, 2011-12-30 16:54:42]

PTAL

The scavenger does not piggyback anymore on timer's proc but uses a
standalone idling scheme (enter/exitsyscall as for the timer).
It seems to solve a bunch of side issues wrt deadlock detection, the
three toy deadlock situations I previously posted now pass without
nasty timeliness glitches.

The additional `runtime·sched.gwait == 0 condition' is here for
transient situations where scavenger's proc is just runnable and some
other proc is being granted with the run opportunity.

Sebastien

[dvyukov, 2012-01-11 17:08:39]

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/malloc.h
File src/pkg/runtime/malloc.h (right):

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:317: int64   unusedsince;	// First time spotted by gc
in MSpanFree state
start the comment with lowercase
s/gc/GC

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mem.go
File src/pkg/runtime/mem.go (right):

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mem.go#newco...
src/pkg/runtime/mem.go:39: NextGC       uint64 // next run in HeapAlloc (bytes)
in HeapAlloc *time*

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

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:361: for(;;) {
perhaps for(k=0;; k++)?

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:362: g->status = Gwaiting;
remove

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:363: g->waitreason = "scavenger goroutine (idle)";
remove
the goroutine will be in syscall status and the waitreason ignored

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:388: if(s->state == MSpanFree && s->unusedsince != 0 &&
(now - s->unusedsince) > grace) {
You seem to carefully iterate over only free spans and then check for MSpanFree
anyway. It is confusing. Replace the check with "assert" (grep for
runtime.throw).
Or actually I would prefer to just scan through runtime·mheap.allspans and check
for MSpanFree spans.

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:398: k += 1;
some messages are output before the line and some - after the line, so they will
have different ids...
I think for(k=0;; k++) is clearer and avoids the problem

[dvyukov, 2012-01-11 18:06:19]

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

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:586: if(runtime·sched.grunning == 1 &&
runtime·sched.gwait == 0)
Can't the scavenger goroutine be in Gwaiting state (when blocked on gcsema)?
Then it's accounted neither in grunning nor in gwait, and we can get a spurious
deadlock report...

[dvyukov, 2012-01-12 14:42:44]

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

http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:327: // TODO(rsc): IncrementalScavenge() to return
memory to OS.
remove

[Sebastien Paolacci, 2012-01-14 10:21:22]

 src/pkg/runtime/malloc.h:317: int64   unusedsince;      // First time
> spotted
> by gc in MSpanFree state
> start the comment with lowercase
> s/gc/GC
Done.

> http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mem.go
> File src/pkg/runtime/mem.go (right):
>
>
http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mem.go#newco...
> src/pkg/runtime/mem.go:39: NextGC       uint64 // next run in HeapAlloc
> (bytes)
> in HeapAlloc *time*
Done.

> src/pkg/runtime/mheap.c:361: for(;;) {
> perhaps for(k=0;; k++)?
Yes, much better.

>
http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:362: g->status = Gwaiting;
> remove
Fixed.

> src/pkg/runtime/mheap.c:363: g->waitreason = "scavenger goroutine
> (idle)";
> remove
> the goroutine will be in syscall status and the waitreason ignored
Done. Timer's proc usage reminiscences...

>
http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:388: if(s->state == MSpanFree && s->unusedsince
> != 0 && (now - s->unusedsince) > grace) {
> You seem to carefully iterate over only free spans and then check for
> MSpanFree anyway. It is confusing. Replace the check with "assert" (grep
> for runtime.throw).
> Or actually I would prefer to just scan through runtime·mheap.allspans
> and check for MSpanFree spans.
Extra check removed, definitely useless since `MSpanIdle' was removed.
I'm not sure however to see the advantage in scanning the whole `allspans' list:
 - it can be quite large as you spotted in scavenger's GC-side
section, larger than freelists anyway.
 - I don't expect to find free spans anywhere but in those freelists,
at least I hope...
Did I miss something?

>
http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:398: k += 1;
> some messages are output before the line and some - after the line, so
> they will have different ids...
> I think for(k=0;; k++) is clearer and avoids the problem
Fixed.

> src/pkg/runtime/proc.c:586: if(runtime·sched.grunning == 1 &&
> runtime·sched.gwait == 0)
> Can't the scavenger goroutine be in Gwaiting state (when blocked on
> gcsema)? Then it's accounted neither in grunning nor in gwait, and we
> can get a spurious deadlock report...
Hum... not nice indeed. Thanks for spotting that, false positives are
definitely not affordable here.
I'm reintroducing the `scvg' identifier to remove the ambiguity on
that active g.

> src/pkg/runtime/mheap.c:327: // TODO(rsc): IncrementalScavenge() to
> return memory to OS.
> remove
Done.

Sebastien

[Sebastien Paolacci, 2012-01-14 10:23:15]

Hello golang-dev@googlegroups.com, rsc@golang.org, dvyukov@google.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2012-01-15 13:43:52]

other than that LGTM
generally it looks like it may work :)
leaving for rsc

http://codereview.appspot.com/5451057/diff/31002/src/pkg/runtime/mem.go
File src/pkg/runtime/mem.go (right):

http://codereview.appspot.com/5451057/diff/31002/src/pkg/runtime/mem.go#newco...
src/pkg/runtime/mem.go:39: NextGC       uint64 // next run in HeapAlloc *time*
(bytes)
:)
please remove the asterisks, I used them to highlight what needs to be added
that's user-visible comments

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

http://codereview.appspot.com/5451057/diff/31002/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:590: for(gp = runtime·allg; gp != nil; gp = gp->alllink)
{
since we already have the pointer to the scavenger, can't it be just
&& (scvg->status == Grunning || scvg->status == Gsyscall)
(no need to scan all g's)?

[dvyukov, 2012-01-15 13:45:08]

2012/1/14 Sébastien Paolacci <sebastien.paolacci@gmail.com>

> >
>
http://codereview.appspot.com/5451057/diff/25006/src/pkg/runtime/mheap.c#newc...
> > src/pkg/runtime/mheap.c:388: if(s->state == MSpanFree && s->unusedsince
> > != 0 && (now - s->unusedsince) > grace) {
> > You seem to carefully iterate over only free spans and then check for
> > MSpanFree anyway. It is confusing. Replace the check with "assert" (grep
> > for runtime.throw).
> > Or actually I would prefer to just scan through runtime·mheap.allspans
> > and check for MSpanFree spans.
> Extra check removed, definitely useless since `MSpanIdle' was removed.
> I'm not sure however to see the advantage in scanning the whole `allspans'
> list:
>  - it can be quite large as you spotted in scavenger's GC-side
> section, larger than freelists anyway.
>  - I don't expect to find free spans anywhere but in those freelists,
> at least I hope...
> Did I miss something?


I think your current code is correct.

[Sebastien Paolacci, 2012-01-23 12:43:41]

>
http://codereview.appspot.com/5451057/diff/31002/src/pkg/runtime/mem.go#newco...
> src/pkg/runtime/mem.go:39: NextGC       uint64 // next run in HeapAlloc
> *time* (bytes)
> :)
> please remove the asterisks, I used them to highlight what needs to be
> added
> that's user-visible comments
I thought you were actually trying to emphasize the unusual `time'
meaning here. Done.

>
http://codereview.appspot.com/5451057/diff/31002/src/pkg/runtime/proc.c#newco...
> src/pkg/runtime/proc.c:590: for(gp = runtime·allg; gp != nil; gp =
> gp->alllink) {
> since we already have the pointer to the scavenger, can't it be just
> && (scvg->status == Grunning || scvg->status == Gsyscall)
> (no need to scan all g's)?
That's correct, looking for a pointer I already pinned is a bit...
thanks. Fixed.

[Sebastien Paolacci, 2012-01-23 12:44:14]

Hello golang-dev@googlegroups.com, rsc@golang.org, dvyukov@google.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-02-06 18:59:50]

Thanks for the reminder.  This was on my list but it needed to be bumped up.
Except for the new environment variables, it looks great.

http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/malloc.h
File src/pkg/runtime/malloc.h (right):

http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:388: void	runtime·MHeap_Scavenger();
(void)

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

http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:332: runtime·MHeap_Scavenger()
(void)

http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:344: env = runtime·getenv("GOSCVGPERIOD");
Sorry, but we have too many environment variables.  We need fewer, not more.
Let's just define some good defaults and leave it at that.

uint64 forcegc;
uint64 limit;

// 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;

[remyoudompheng, 2012-02-07 06:50:22]

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

http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
src/pkg/runtime/mheap.c:398: k, mstats.heap_inuse>>20, mstats.heap_idle>>20,
mstats.heap_sys>>20,
I get "warning: format mismatch D UINT, arg 3" from 8c when compiling with
GOARCH=386, there might be a cast/conversion missing, %D expects a (u)int64.

[Sebastien Paolacci, 2012-02-07 13:20:40]

On Mon, Feb 6, 2012 at 7:59 PM,  <rsc@golang.org> wrote:
> Thanks for the reminder.  This was on my list but it needed to be bumped
> up.
> Except for the new environment variables, it looks great.
>
>
>
> http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/malloc.h
> File src/pkg/runtime/malloc.h (right):
>
>
http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/malloc.h#new...
> src/pkg/runtime/malloc.h:388: void      runtime·MHeap_Scavenger();
> (void)
Done.

>
http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:332: runtime·MHeap_Scavenger()
> (void)
Done.

>
http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:344: env = runtime·getenv("GOSCVGPERIOD");
> Sorry, but we have too many environment variables.
You don't have to be, they're just here for testing purpose. Let's go
on if "anyone" is fine with the now defaults.

> uint64 forcegc;
> uint64 limit;
>
> // 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;
Done. CL description updated with that info too.

Sebastien

[Sebastien Paolacci, 2012-02-07 13:32:04]

On Tue, Feb 7, 2012 at 7:50 AM,  <remyoudompheng@gmail.com> wrote:
>
>
http://codereview.appspot.com/5451057/diff/38001/src/pkg/runtime/mheap.c#newc...
> src/pkg/runtime/mheap.c:398: k, mstats.heap_inuse>>20,
> mstats.heap_idle>>20, mstats.heap_sys>>20,
> I get "warning: format mismatch D UINT, arg 3" from 8c when compiling
> with GOARCH=386, there might be a cast/conversion missing, %D expects a
> (u)int64.
Fixed, thanks. Since you gave that deeper look (or just fed your
numerical formatting love ;)), any opinion on the now hardcoded
constants and overall behavior?

Sebastien

[Sebastien Paolacci, 2012-02-07 13:32:56]

Hello rsc@golang.org, dvyukov@google.com, remyoudompheng@gmail.com (cc:
golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2012-02-09 22:04:55]

The constants seem a bit large to see an effect when running programs by hand,
but they seem OK for use by long-running daemons.

Rémy.

[rsc, 2012-02-16 18:29:54]

LGTM

I got to play with this last night, and it worked nicely.
Thanks very much.

[rsc, 2012-02-16 18:30:09]

*** Submitted as http://code.google.com/p/go/source/detail?r=b96e722aad5a ***

runtime: release unused memory to the OS.

Periodically browse MHeap's freelists for long unused spans and release them if
any.

Current hardcoded settings:
        - GC is forced if none occured over the last 2 minutes.
        - spans are handed back after 5 minutes of uselessness.

SysUnused (for Unix) is a wrapper on madvise MADV_DONTNEED on Linux and
MADV_FREE on BSDs.

R=rsc, dvyukov, remyoudompheng
CC=golang-dev
http://codereview.appspot.com/5451057

Committer: Russ Cox <rsc@golang.org>

[Sebastien Paolacci, 2012-08-06 21:36:34]

*** Abandoned ***