[PATCH v7 04/12] mm: multigenerational LRU: groundwork

[Johannes Weiner]

Hi Yu,

On Mon, Feb 21, 2022 at 01:14:24AM -0700, Yu Zhao wrote:
> On Tue, Feb 15, 2022 at 04:53:56PM -0500, Johannes Weiner wrote:
> > On Tue, Feb 15, 2022 at 02:43:05AM -0700, Yu Zhao wrote:
> > > On Thu, Feb 10, 2022 at 03:41:57PM -0500, Johannes Weiner wrote:
> > > > > +static inline bool lru_gen_is_active(struct lruvec *lruvec, int gen)
> > > > > +{
> > > > > +	unsigned long max_seq = lruvec->lrugen.max_seq;
> > > > > +
> > > > > +	VM_BUG_ON(gen >= MAX_NR_GENS);
> > > > > +
> > > > > +	/* see the comment on MIN_NR_GENS */
> > > > > +	return gen == lru_gen_from_seq(max_seq) || gen == lru_gen_from_seq(max_seq - 1);
> > > > > +}
> > > > 
> > > > I'm still reading the series, so correct me if I'm wrong: the "active"
> > > > set is split into two generations for the sole purpose of the
> > > > second-chance policy for fresh faults, right?
> > > 
> > > To be precise, the active/inactive notion on top of generations is
> > > just for ABI compatibility, e.g., the counters in /proc/vmstat.
> > > Otherwise, this function wouldn't be needed.
> > 
> > Ah! would you mind adding this as a comment to the function?
> 
> Will do.
> 
> > But AFAICS there is the lru_gen_del_folio() callsite that maps it to
> > the PG_active flag - which in turn gets used by add_folio() to place
> > the thing back on the max_seq generation. So I suppose there is a
> > secondary purpose of the function for remembering the page's rough age
> > for non-reclaim isolation.>
> 
> Yes, e.g., migration.

Ok, thanks for clarifying. That should also be in the comment.

On scan resistance:

> > The concern isn't the scan overhead, but jankiness from the workingset
> > being flooded out by streaming IO.
> 
> Yes, MGLRU uses a different approach to solve this problem, and for
> its approach, the scan overhead is the concern.
> 
> MGLRU detects (defines) the working set by scanning the entire memory
> for each generation, and it counters the flooding by accelerating the
> creation of generations. IOW, all mapped pages have an equal chance to
> get scanned, no matter which generation they are in. This is a design
> difference compared with the active/inactive LRU, which tries to scans
> the active/inactive lists less/more frequently.
>
> > The concrete usecase at the time was a torrent client hashing a
> > downloaded file and thereby kicking out the desktop environment, which
> > caused jankiness. The hashing didn't benefit from caching - the file
> > wouldn't have fit into RAM anyway - so this was pointless to boot.
> > 
> > Essentially, the tradeoff is this:
> > 
> > 1) If you treat new pages as hot, you accelerate workingset
> > transitions, but on the flipside you risk unnecessary refaults in
> > running applications when those new pages are one-off.
> > 
> > 2) If you take new pages with a grain of salt, you protect existing
> > applications better from one-off floods, but risk refaults in NEW
> > application while they're trying to start up.
> 
> Agreed.
> 
> > There are two arguments for why 2) is preferable:
> > 
> > 1) Users are tolerant of cache misses when applications first launch,
> >    much less so after they've been running for hours.
> 
> Our CUJs (Critical User Journeys) respectfully disagree :)
> 
> They are built on the observation that once users have moved onto
> another tab/app, they are more likely to stay with the new tab/app
> rather than go back to the old ones. Speaking for myself, this is
> generally the case.

That's in line with what I said. Where is the disagreement?

> > 2) Workingset transitions (and associated jankiness) are bounded by
> >    the amount of RAM you need to repopulate. But streaming IO is
> >    bounded by storage, and datasets are routinely several times the
> >    amount of RAM. Uncacheable sets in excess of RAM can produce an
> >    infinite stream of "new" references; not protecting the workingset
> >    from that means longer or even sustained jankiness.
> 
> I'd argue the opposite -- we shouldn't risk refaulting fresh hot pages
> just to accommodate this concrete yet minor use case, especially
> considering torrent has been given the means (MADV_SEQUENTIAL) to help
> itself.
>
> I appreciate all your points here. The bottom line is we agree this is
> a trade off. For what disagree about, we could be both right -- it
> comes down to what workloads we care about *more*.

It's a straight-forward question: How does MGLRU avoid cache pollution
from scans?

Your answer above seems to be "it just does". Your answer here seems
to be "it doesn't, but it doesn't matter". Forgive me if I'm
misreading what you're saying.

But it's not a minor concern. Read the motivation behind any modern
cache algorithm - ARC, LIRS, Clock-Pro, LRU-K, 2Q - and scan
resistance is the reason for why they all exist in the first place.


    "The LRU-K algorithm surpasses conventional buffering algorithms
     in discriminating between frequently and infrequently referenced
     pages."

        - The LRU-K page replacement algorithm for database disk
          buffering, O'Neil et al, 1993

    "Although LRU replacement policy has been commonly used in the
     buffer cache management, it is well known for its inability to
     cope with access patterns with weak locality."

        - LIRS: an efficient low inter-reference recency set
         replacement policy to improve buffer cache performance,
         Jiang, Zhang, 2002

    "The self-tuning, low-overhead, scan-resistant adaptive
     replacement cache algorithm outperforms the least-recently-used
     algorithm by dynamically responding to changing access patterns
     and continually balancing between workload recency and frequency
     features."

        - Outperforming LRU with an adaptive replacement cache
          algorithm, Megiddo, Modha, 2004

    "Over the last three decades, the inability of LRU as well as
     CLOCK to handle weak locality accesses has become increasingly
     serious, and an effective fix becomes increasingly desirable.

        - CLOCK-Pro: An Effective Improvement of the CLOCK
          Replacement, Jiang et al, 2005


We can't rely on MADV_SEQUENTIAL alone. Not all accesses know in
advance that they'll be one-off; it can be a group of uncoordinated
tasks causing the pattern etc.

This is a pretty fundamental issue. It would be good to get a more
satisfying answer on this.

> > > > You can drop the memcg parameter and use lruvec_memcg().
> > > 
> > > lruvec_memcg() isn't available yet when pgdat_init_internals() calls
> > > this function because mem_cgroup_disabled() is initialized afterward.
> > 
> > Good catch. That'll container_of() into garbage. However, we have to
> > assume that somebody's going to try that simplification again, so we
> > should set up the code now to prevent issues.
> > 
> > cgroup_disable parsing is self-contained, so we can pull it ahead in
> > the init sequence. How about this?
> > 
> > diff --git a/kernel/cgroup/cgroup.c b/kernel/cgroup/cgroup.c
> > index 9d05c3ca2d5e..b544d768edc8 100644
> > --- a/kernel/cgroup/cgroup.c
> > +++ b/kernel/cgroup/cgroup.c
> > @@ -6464,9 +6464,9 @@ static int __init cgroup_disable(char *str)
> >  			break;
> >  		}
> >  	}
> > -	return 1;
> > +	return 0;
> >  }
> > -__setup("cgroup_disable=", cgroup_disable);
> > +early_param("cgroup_disable", cgroup_disable);
> 
> I think early_param() is still after pgdat_init_internals(), no?

It's called twice for some reason, but AFAICS the first one is always
called before pgdat_init_internals():

start_kernel()
  setup_arch()
    parse_early_param()
    x86_init.paging.pagetable_init();
      paging_init()
        zone_sizes_init()
          free_area_init()
            free_area_init_node()
              free_area_init_core()
                pgdat_init_internals()
  parse_early_param()

It's the same/similar for arm, sparc and mips.