From: Yu Zhao <yuzhao@google.com>
To: Barry Song <21cnbao@gmail.com>
Cc: "Stephen Rothwell" <sfr@rothwell.id.au>,
Linux-MM <linux-mm@kvack.org>, "Andi Kleen" <ak@linux.intel.com>,
"Andrew Morton" <akpm@linux-foundation.org>,
"Aneesh Kumar" <aneesh.kumar@linux.ibm.com>,
"Catalin Marinas" <catalin.marinas@arm.com>,
"Dave Hansen" <dave.hansen@linux.intel.com>,
"Hillf Danton" <hdanton@sina.com>, "Jens Axboe" <axboe@kernel.dk>,
"Jesse Barnes" <jsbarnes@google.com>,
"Johannes Weiner" <hannes@cmpxchg.org>,
"Jonathan Corbet" <corbet@lwn.net>,
"Linus Torvalds" <torvalds@linux-foundation.org>,
"Matthew Wilcox" <willy@infradead.org>,
"Mel Gorman" <mgorman@suse.de>,
"Michael Larabel" <Michael@michaellarabel.com>,
"Michal Hocko" <mhocko@kernel.org>,
"Mike Rapoport" <rppt@kernel.org>,
"Rik van Riel" <riel@surriel.com>,
"Vlastimil Babka" <vbabka@suse.cz>,
"Will Deacon" <will@kernel.org>,
"Ying Huang" <ying.huang@intel.com>,
LAK <linux-arm-kernel@lists.infradead.org>,
"Linux Doc Mailing List" <linux-doc@vger.kernel.org>,
LKML <linux-kernel@vger.kernel.org>,
"Kernel Page Reclaim v2" <page-reclaim@google.com>,
x86 <x86@kernel.org>, "Brian Geffon" <bgeffon@google.com>,
"Jan Alexander Steffens" <heftig@archlinux.org>,
"Oleksandr Natalenko" <oleksandr@natalenko.name>,
"Steven Barrett" <steven@liquorix.net>,
"Suleiman Souhlal" <suleiman@google.com>,
"Daniel Byrne" <djbyrne@mtu.edu>,
"Donald Carr" <d@chaos-reins.com>,
"Holger Hoffstätte" <holger@applied-asynchrony.com>,
"Konstantin Kharlamov" <Hi-Angel@yandex.ru>,
"Shuang Zhai" <szhai2@cs.rochester.edu>,
"Sofia Trinh" <sofia.trinh@edi.works>,
"Vaibhav Jain" <vaibhav@linux.ibm.com>
Subject: Re: [PATCH v10 06/14] mm: multi-gen LRU: minimal implementation
Date: Tue, 19 Apr 2022 16:20:47 -0600 [thread overview]
Message-ID: <CAOUHufYmQNLwYNE0BnOV_8-GB1pCZaGQcmejCYF5qyhKQaozUA@mail.gmail.com> (raw)
In-Reply-To: <CAGsJ_4wj2mbqSoT3sXHVU+ouCpTPyOXAu9wZS+2U_T5LtN97dA@mail.gmail.com>
On Mon, Apr 18, 2022 at 10:26 PM Barry Song <21cnbao@gmail.com> wrote:
>
> On Tue, Apr 19, 2022 at 12:54 PM Yu Zhao <yuzhao@google.com> wrote:
> >
> > On Mon, Apr 18, 2022 at 3:58 AM Barry Song <21cnbao@gmail.com> wrote:
> > >
> > > On Thu, Apr 7, 2022 at 3:16 PM Yu Zhao <yuzhao@google.com> wrote:
> > > >
> > > > To avoid confusion, the terms "promotion" and "demotion" will be
> > > > applied to the multi-gen LRU, as a new convention; the terms
> > > > "activation" and "deactivation" will be applied to the active/inactive
> > > > LRU, as usual.
> > > >
> > > > The aging produces young generations. Given an lruvec, it increments
> > > > max_seq when max_seq-min_seq+1 approaches MIN_NR_GENS. The aging
> > > > promotes hot pages to the youngest generation when it finds them
> > > > accessed through page tables; the demotion of cold pages happens
> > > > consequently when it increments max_seq. The aging has the complexity
> > > > O(nr_hot_pages), since it is only interested in hot pages. Promotion
> > > > in the aging path does not require any LRU list operations, only the
> > > > updates of the gen counter and lrugen->nr_pages[]; demotion, unless as
> > > > the result of the increment of max_seq, requires LRU list operations,
> > > > e.g., lru_deactivate_fn().
> > > >
> > > > The eviction consumes old generations. Given an lruvec, it increments
> > > > min_seq when the lists indexed by min_seq%MAX_NR_GENS become empty. A
> > > > feedback loop modeled after the PID controller monitors refaults over
> > > > anon and file types and decides which type to evict when both types
> > > > are available from the same generation.
> > > >
> > > > Each generation is divided into multiple tiers. Tiers represent
> > > > different ranges of numbers of accesses through file descriptors. A
> > > > page accessed N times through file descriptors is in tier
> > > > order_base_2(N). Tiers do not have dedicated lrugen->lists[], only
> > > > bits in folio->flags. In contrast to moving across generations, which
> > > > requires the LRU lock, moving across tiers only involves operations on
> > > > folio->flags. The feedback loop also monitors refaults over all tiers
> > > > and decides when to protect pages in which tiers (N>1), using the
> > > > first tier (N=0,1) as a baseline. The first tier contains single-use
> > > > unmapped clean pages, which are most likely the best choices. The
> > > > eviction moves a page to the next generation, i.e., min_seq+1, if the
> > > > feedback loop decides so. This approach has the following advantages:
> > > > 1. It removes the cost of activation in the buffered access path by
> > > > inferring whether pages accessed multiple times through file
> > > > descriptors are statistically hot and thus worth protecting in the
> > > > eviction path.
> > > > 2. It takes pages accessed through page tables into account and avoids
> > > > overprotecting pages accessed multiple times through file
> > > > descriptors. (Pages accessed through page tables are in the first
> > > > tier, since N=0.)
> > > > 3. More tiers provide better protection for pages accessed more than
> > > > twice through file descriptors, when under heavy buffered I/O
> > > > workloads.
> > > >
> > >
> > > Hi Yu,
> > > As I told you before, I tried to change the current LRU (not MGLRU) by only
> > > promoting unmapped file pages to the head of the inactive head rather than
> > > the active head on its second access:
> > > https://lore.kernel.org/lkml/CAGsJ_4y=TkCGoWWtWSAptW4RDFUEBeYXwfwu=fUFvV4Sa4VA4A@mail.gmail.com/
> > > I have already seen some very good results by the decease of cpu consumption of
> > > kswapd and direct reclamation in the testing.
> >
> > Glad to hear. I suspected you'd see some good results with that change :)
> >
> > > in mglru, it seems "twice" isn't a concern at all, one unmapped file
> > > page accessed
> > > twice has no much difference with those ones which are accessed once as you
> > > only begin to increase refs from the third time:
> >
> > refs are *additional* accesses:
> > PG_referenced: N=1
> > PG_referenced+PG_workingset: N=2
> > PG_referenced+PG_workingset+refs: N=3,4,5
> >
> > When N=2, order_base_2(N)=1. So pages accessed twice are in the second
> > tier. Therefore they are "different".
> >
> > More details [1]:
> >
> > +/*
> > + * Each generation is divided into multiple tiers. Tiers represent different
> > + * ranges of numbers of accesses through file descriptors. A page accessed N
> > + * times through file descriptors is in tier order_base_2(N). A page in the
> > + * first tier (N=0,1) is marked by PG_referenced unless it was faulted in
> > + * though page tables or read ahead. A page in any other tier (N>1) is marked
> > + * by PG_referenced and PG_workingset.
> > + *
> > + * In contrast to moving across generations which requires the LRU lock, moving
> > + * across tiers only requires operations on folio->flags and therefore has a
> > + * negligible cost in the buffered access path. In the eviction path,
> > + * comparisons of refaulted/(evicted+protected) from the first tier and the
> > + * rest infer whether pages accessed multiple times through file descriptors
> > + * are statistically hot and thus worth protecting.
> > + *
> > + * MAX_NR_TIERS is set to 4 so that the multi-gen LRU can support twice of the
> > + * categories of the active/inactive LRU when keeping track of accesses through
> > + * file descriptors. It requires MAX_NR_TIERS-2 additional bits in
> > folio->flags.
> > + */
> > +#define MAX_NR_TIERS 4U
> >
> > [1] https://lore.kernel.org/linux-mm/20220407031525.2368067-7-yuzhao@google.com/
> >
> > > +static void folio_inc_refs(struct folio *folio)
> > > +{
> > > + unsigned long refs;
> > > + unsigned long old_flags, new_flags;
> > > +
> > > + if (folio_test_unevictable(folio))
> > > + return;
> > > +
> > > + /* see the comment on MAX_NR_TIERS */
> > > + do {
> > > + new_flags = old_flags = READ_ONCE(folio->flags);
> > > +
> > > + if (!(new_flags & BIT(PG_referenced))) {
> > > + new_flags |= BIT(PG_referenced);
> > > + continue;
> > > + }
> > > +
> > > + if (!(new_flags & BIT(PG_workingset))) {
> > > + new_flags |= BIT(PG_workingset);
> > > + continue;
> > > + }
> > > +
> > > + refs = new_flags & LRU_REFS_MASK;
> > > + refs = min(refs + BIT(LRU_REFS_PGOFF), LRU_REFS_MASK);
> > > +
> > > + new_flags &= ~LRU_REFS_MASK;
> > > + new_flags |= refs;
> > > + } while (new_flags != old_flags &&
> > > + cmpxchg(&folio->flags, old_flags, new_flags) != old_flags);
> > > +}
> > >
> > > So my question is what makes you so confident that twice doesn't need
> > > any special treatment while the vanilla kernel is upgrading this kind of page
> > > to the head of the active instead? I am asking this because I am considering
> > > reclaiming unmapped file pages which are only accessed twice when they
> > > get to the tail of the inactive list.
> >
> > Per above, pages accessed twice are in their own tier. Hope this clarifies it.
>
> Yep, I found the trick here , "+1" is magic behind the code, haha.
>
> +static int folio_lru_tier(struct folio *folio)
> +{
> + int refs;
> + unsigned long flags = READ_ONCE(folio->flags);
> +
> + refs = (flags & LRU_REFS_FLAGS) == LRU_REFS_FLAGS ?
> + ((flags & LRU_REFS_MASK) >> LRU_REFS_PGOFF) + 1 : 0;
> +
> + return lru_tier_from_refs(refs);
> +}
> +
>
> TBH, this might need some comments, otherwise, it is easy to misunderstand
> we are beginning to have protection from 3rd access :-)
Agreed. Let me rework this function. I don't know how yet but I'll
think of something.
next prev parent reply other threads:[~2022-04-19 22:21 UTC|newest]
Thread overview: 99+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-04-07 3:15 [PATCH v10 00/14] Multi-Gen LRU Framework Yu Zhao
2022-04-07 3:15 ` [PATCH v10 01/14] mm: x86, arm64: add arch_has_hw_pte_young() Yu Zhao
2022-04-07 3:15 ` [PATCH v10 02/14] mm: x86: add CONFIG_ARCH_HAS_NONLEAF_PMD_YOUNG Yu Zhao
2022-04-07 3:15 ` [PATCH v10 03/14] mm/vmscan.c: refactor shrink_node() Yu Zhao
2022-04-16 6:48 ` Miaohe Lin
2022-04-07 3:15 ` [PATCH v10 04/14] Revert "include/linux/mm_inline.h: fold __update_lru_size() into its sole caller" Yu Zhao
2022-04-16 6:50 ` Miaohe Lin
2022-04-07 3:15 ` [PATCH v10 05/14] mm: multi-gen LRU: groundwork Yu Zhao
2022-04-12 2:16 ` Andrew Morton
2022-04-12 7:06 ` Peter Zijlstra
2022-04-20 0:39 ` Yu Zhao
2022-04-20 20:07 ` Linus Torvalds
2022-04-26 22:39 ` Yu Zhao
2022-04-26 23:42 ` Andrew Morton
2022-04-27 1:18 ` Yu Zhao
2022-04-27 1:34 ` Andrew Morton
2022-04-07 3:15 ` [PATCH v10 06/14] mm: multi-gen LRU: minimal implementation Yu Zhao
2022-04-14 6:03 ` Barry Song
2022-04-14 20:36 ` Yu Zhao
2022-04-14 21:39 ` Andrew Morton
2022-04-14 22:14 ` Yu Zhao
2022-04-15 10:15 ` Barry Song
2022-04-15 20:17 ` Yu Zhao
2022-04-15 10:26 ` Barry Song
2022-04-15 20:18 ` Yu Zhao
2022-04-14 11:47 ` Chen Wandun
2022-04-14 20:53 ` Yu Zhao
2022-04-15 2:23 ` Chen Wandun
2022-04-15 5:25 ` Yu Zhao
2022-04-15 6:31 ` Chen Wandun
2022-04-15 6:44 ` Yu Zhao
2022-04-15 9:27 ` Chen Wandun
2022-04-18 9:58 ` Barry Song
2022-04-19 0:53 ` Yu Zhao
2022-04-19 4:25 ` Barry Song
2022-04-19 4:36 ` Barry Song
2022-04-19 22:25 ` Yu Zhao
2022-04-19 22:20 ` Yu Zhao [this message]
2022-04-07 3:15 ` [PATCH v10 07/14] mm: multi-gen LRU: exploit locality in rmap Yu Zhao
2022-04-27 4:32 ` Aneesh Kumar K.V
2022-04-27 4:38 ` Yu Zhao
2022-04-27 5:31 ` Aneesh Kumar K V
2022-04-27 6:00 ` Yu Zhao
2022-04-07 3:15 ` [PATCH v10 08/14] mm: multi-gen LRU: support page table walks Yu Zhao
2022-04-12 2:16 ` Andrew Morton
2022-04-12 7:10 ` Peter Zijlstra
2022-04-15 5:30 ` Yu Zhao
2022-04-15 1:14 ` Yu Zhao
2022-04-15 1:56 ` Andrew Morton
2022-04-15 6:25 ` Yu Zhao
2022-04-15 19:15 ` Andrew Morton
2022-04-15 20:11 ` Yu Zhao
2022-04-15 21:32 ` Andrew Morton
2022-04-15 21:36 ` Linus Torvalds
2022-04-15 22:57 ` Yu Zhao
2022-04-15 23:03 ` Linus Torvalds
2022-04-15 23:24 ` [page-reclaim] " Jesse Barnes
2022-04-15 23:31 ` Matthew Wilcox
2022-04-15 23:37 ` Jesse Barnes
2022-04-15 23:49 ` Yu Zhao
2022-04-16 16:32 ` Justin Forbes
2022-04-19 22:32 ` Yu Zhao
2022-04-29 14:10 ` zhong jiang
2022-04-30 8:34 ` Yu Zhao
2022-04-07 3:15 ` [PATCH v10 09/14] mm: multi-gen LRU: optimize multiple memcgs Yu Zhao
2022-04-07 3:15 ` [PATCH v10 10/14] mm: multi-gen LRU: kill switch Yu Zhao
2022-04-12 2:16 ` Andrew Morton
2022-04-26 20:57 ` Yu Zhao
2022-04-26 22:22 ` Andrew Morton
2022-04-27 1:11 ` Yu Zhao
2022-04-07 3:15 ` [PATCH v10 11/14] mm: multi-gen LRU: thrashing prevention Yu Zhao
2022-04-07 3:15 ` [PATCH v10 12/14] mm: multi-gen LRU: debugfs interface Yu Zhao
2022-04-12 2:16 ` Andrew Morton
2022-04-16 0:03 ` Yu Zhao
2022-04-16 4:20 ` Andrew Morton
2022-04-26 6:59 ` Yu Zhao
2022-04-26 21:30 ` Andrew Morton
2022-04-26 22:15 ` Yu Zhao
2022-04-07 3:15 ` [PATCH v10 13/14] mm: multi-gen LRU: admin guide Yu Zhao
2022-04-07 12:41 ` Bagas Sanjaya
2022-04-07 12:51 ` Jonathan Corbet
2022-04-12 2:16 ` Andrew Morton
2022-04-16 2:22 ` Yu Zhao
2022-04-07 3:15 ` [PATCH v10 14/14] mm: multi-gen LRU: design doc Yu Zhao
2022-04-07 11:39 ` Huang Shijie
2022-04-07 12:41 ` Bagas Sanjaya
2022-04-07 12:52 ` Jonathan Corbet
2022-04-08 4:48 ` Bagas Sanjaya
2022-04-12 2:16 ` Andrew Morton
2022-04-26 7:42 ` Yu Zhao
2022-04-07 3:24 ` [PATCH v10 00/14] Multi-Gen LRU Framework Yu Zhao
2022-04-07 8:31 ` Stephen Rothwell
2022-04-07 9:08 ` Yu Zhao
2022-04-07 9:41 ` Yu Zhao
2022-04-07 12:13 ` Stephen Rothwell
2022-04-08 2:08 ` Yu Zhao
2022-04-12 2:15 ` Andrew Morton
2022-04-14 5:06 ` Andrew Morton
2022-04-20 0:50 ` Yu Zhao
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAOUHufYmQNLwYNE0BnOV_8-GB1pCZaGQcmejCYF5qyhKQaozUA@mail.gmail.com \
--to=yuzhao@google.com \
--cc=21cnbao@gmail.com \
--cc=Hi-Angel@yandex.ru \
--cc=Michael@michaellarabel.com \
--cc=ak@linux.intel.com \
--cc=akpm@linux-foundation.org \
--cc=aneesh.kumar@linux.ibm.com \
--cc=axboe@kernel.dk \
--cc=bgeffon@google.com \
--cc=catalin.marinas@arm.com \
--cc=corbet@lwn.net \
--cc=d@chaos-reins.com \
--cc=dave.hansen@linux.intel.com \
--cc=djbyrne@mtu.edu \
--cc=hannes@cmpxchg.org \
--cc=hdanton@sina.com \
--cc=heftig@archlinux.org \
--cc=holger@applied-asynchrony.com \
--cc=jsbarnes@google.com \
--cc=linux-arm-kernel@lists.infradead.org \
--cc=linux-doc@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mgorman@suse.de \
--cc=mhocko@kernel.org \
--cc=oleksandr@natalenko.name \
--cc=page-reclaim@google.com \
--cc=riel@surriel.com \
--cc=rppt@kernel.org \
--cc=sfr@rothwell.id.au \
--cc=sofia.trinh@edi.works \
--cc=steven@liquorix.net \
--cc=suleiman@google.com \
--cc=szhai2@cs.rochester.edu \
--cc=torvalds@linux-foundation.org \
--cc=vaibhav@linux.ibm.com \
--cc=vbabka@suse.cz \
--cc=will@kernel.org \
--cc=willy@infradead.org \
--cc=x86@kernel.org \
--cc=ying.huang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).