Re: [PATCH v1 09/14] mm: multigenerational lru: mm_struct list

[Yu Zhao <yuzhao@google.com>]

On Wed, Mar 17, 2021 at 11:37:38AM +0800, Huang, Ying wrote:
> Yu Zhao <yuzhao@google.com> writes:
> 
> > On Tue, Mar 16, 2021 at 02:44:31PM +0800, Huang, Ying wrote:
> >> Yu Zhao <yuzhao@google.com> writes:
> >> 
> >> > On Tue, Mar 16, 2021 at 10:07:36AM +0800, Huang, Ying wrote:
> >> >> Rik van Riel <riel@surriel.com> writes:
> >> >> 
> >> >> > On Sat, 2021-03-13 at 00:57 -0700, Yu Zhao wrote:
> >> >> >
> >> >> >> +/*
> >> >> >> + * After pages are faulted in, they become the youngest generation.
> >> >> >> They must
> >> >> >> + * go through aging process twice before they can be evicted. After
> >> >> >> first scan,
> >> >> >> + * their accessed bit set during initial faults are cleared and they
> >> >> >> become the
> >> >> >> + * second youngest generation. And second scan makes sure they
> >> >> >> haven't been used
> >> >> >> + * since the first.
> >> >> >> + */
> >> >> >
> >> >> > I have to wonder if the reductions in OOM kills and 
> >> >> > low-memory tab discards is due to this aging policy
> >> >> > change, rather than from the switch to virtual scanning.
> >> >
> >> > There are no policy changes per se. The current page reclaim also
> >> > scans a faulted-in page at least twice before it can reclaim it.
> >> > That said, the new aging yields a better overall result because it
> >> > discovers every page that has been referenced since the last scan,
> >> > in addition to what Ying has mentioned. The current page scan stops
> >> > stops once it finds enough candidates, which may seem more
> >> > efficiently, but actually pays the price for not finding the best.
> >> >
> >> >> If my understanding were correct, the temperature of the processes is
> >> >> considered in addition to that of the individual pages.  That is, the
> >> >> pages of the processes that haven't been scheduled after the previous
> >> >> scanning will not be scanned.  I guess that this helps OOM kills?
> >> >
> >> > Yes, that's correct.
> >> >
> >> >> If so, how about just take advantage of that information for OOM killing
> >> >> and page reclaiming?  For example, if a process hasn't been scheduled
> >> >> for long time, just reclaim its private pages.
> >> >
> >> > This is how it works. Pages that haven't been scanned grow older
> >> > automatically because those that have been scanned will be tagged with
> >> > younger generation numbers. Eviction does bucket sort based on
> >> > generation numbers and attacks the oldest.
> >> 
> >> Sorry, my original words are misleading.  What I wanted to say was that
> >> is it good enough that
> >> 
> >> - Do not change the core algorithm of current page reclaiming.
> >> 
> >> - Add some new logic to reclaim the process private pages regardless of
> >>   the Accessed bits if the processes are not scheduled for some long
> >>   enough time.  This can be done before the normal page reclaiming.
> >
> > This is a good idea, which being used on Android and Chrome OS. We
> > call it per-process reclaim, and I've mentioned here:
> > https://lore.kernel.org/linux-mm/YBkT6175GmMWBvw3@google.com/
> >   On Android, our most advanced simulation that generates memory
> >   pressure from realistic user behavior shows 18% fewer low-memory
> >   kills, which in turn reduces cold starts by 16%. This is on top of
> >   per-process reclaim, a predecessor of ``MADV_COLD`` and
> >   ``MADV_PAGEOUT``, against background apps.
> 
> Thanks, now I see your improvement compared with the per-process
> reclaim.  How about the per-process reclaim compared with the normal
> page reclaiming for the similar test cases?
> 
> My intention behind this is that your solution includes several
> improvements,
> 
> a) take advantage of scheduler information
> b) more fine-grained active/inactive dividing
> c) page table scanning instead of rmap
> 
> Is it possible to evaluate the benefit of the each step?  And is there
> still some potential to optimize the current LRU based algorithm before
> adopting a totally new algorithm?

Well, there isn't really any new algorithm -- it's still the LRU
(algorithm). But I do see your point. In another survey we posted
here:
https://lore.kernel.org/linux-mm/YBkT6175GmMWBvw3@google.com/
we stated:
  Why not try to improve the existing code?
  -----------------------------------------
  We have tried but concluded the two limiting factors [note]_ in the
  existing code are fundamental, and therefore changes made atop them
  will not result in substantial gains on any of the aspects above.

We learned this the hard way.

> > The patches landed not long a ago :) See mm/madvise.c
> 
> :) I'm too out-dated.
> 
> >> So this is an one small step improvement to the current page reclaiming
> >> algorithm via taking advantage of the scheduler information.  It's
> >> clearly not sophisticated as your new algorithm, for example, the cold
> >> pages in the hot processes will not be reclaimed in this stage.  But it
> >> can reduce the overhead of scanning too.
> >
> > The general problems with the direction of per-process reclaim:
> >   1) we can't find the coldest pages, as you have mentioned.
> >   2) we can't reach file pages accessed via file descriptors only,
> >   especially those caching config files that were read only once.
> 
> In theory, this is possible, we can build a inode list based on the
> accessing time too.  Although this may not be necessary.  We can reclaim
> the read-once file cache before the per-process reclaim in theory.

You have to search for unmapped clean pages in page cache. Generally
searching page cache is a lot more expensive than walking lru lists
because page cache can be sparse but lru lists can't.

> >   3) we can't reclaim lru pages and slab objects proportionally and
> >   therefore we leave many stale slab objects behind.
> >   4) we have to be proactive, as you suggested (once again, you were
> >   right), and this has a serious problem: client's battery life can
> >   be affected.
> 
> Why can this not be done reactively? We can start per-process reclaim
> under memory pressure.

Under memory pressure, we could scan a lot of idle processes and find
nothing to reclaim, e.g., mlockall(). In addition, address spaces can
be sparse too.

You are now looking at the direction of cold memory tracking using
page tables, which is not practical. Apparent this series has given
you a bad idea... Page tables are only good at discovering hot memory.
Take my word for it :)

> This has been used in phone and laptop now, so
> there's a solution for this issue?

madvise() is called based on user behavior, which we don't have in
kernel space.

> > The scanning overhead is only one of the two major problems of the
> > current page reclaim. The other problem is the granularity of the
> > active/inactive (sizes). We stopped using them in making job
> > scheduling decision a long time ago. I know another large internet
> > company adopted a similar approach as ours, and I'm wondering how
> > everybody else is coping with the discrepancy from those counters.
> 
> From intuition, the scanning overhead of the full page table scanning
> appears higher than that of the rmap scanning for a small portion of
> system memory.  But form your words, you think the reality is the
> reverse?  If others concern about the overhead too, finally, I think you
> need to prove the overhead of the page table scanning isn't too higher,
> or even lower with more data and theory.

There is a misunderstanding here. I never said anything about full
page table scanning. And this is not how it's done in this series
either. I guess the misunderstanding has something to do with the cold
memory tracking you are thinking about?

This series uses page tables to discover page accesses when a system
has run out of inactive pages. Under such a situation, the system is
very likely to have a lot of page accesses, and using the rmap is
likely to cost a lot more because its poor memory locality compared
with page tables.

But, page tables can be sparse too, in terms of hot memory tracking.
Dave has asked me to test the worst case scenario, which I'll do.
And I'd be happy to share more data. Any specific workload you are
interested in?