linux-kernel - Re: Re: [PATCH v13 05/15] mm/damon: Adaptively adjust regions

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20200527124635.19577-1-sjpark@amazon.com>
Date:   Wed, 27 May 2020 14:46:35 +0200
From:   SeongJae Park <sjpark@...zon.com>
To:     Leonard Foerster <foersleo@...zon.com>
CC:     SeongJae Park <sjpark@...zon.com>, <akpm@...ux-foundation.org>,
        "SeongJae Park" <sjpark@...zon.de>, <Jonathan.Cameron@...wei.com>,
        <aarcange@...hat.com>, <acme@...nel.org>,
        <alexander.shishkin@...ux.intel.com>, <amit@...nel.org>,
        <benh@...nel.crashing.org>, <brendan.d.gregg@...il.com>,
        <brendanhiggins@...gle.com>, <cai@....pw>,
        <colin.king@...onical.com>, <corbet@....net>, <dwmw@...zon.com>,
        <irogers@...gle.com>, <jolsa@...hat.com>, <kirill@...temov.name>,
        <mark.rutland@....com>, <mgorman@...e.de>, <minchan@...nel.org>,
        <mingo@...hat.com>, <namhyung@...nel.org>, <peterz@...radead.org>,
        <rdunlap@...radead.org>, <riel@...riel.com>, <rientjes@...gle.com>,
        <rostedt@...dmis.org>, <sblbir@...zon.com>, <shakeelb@...gle.com>,
        <shuah@...nel.org>, <sj38.park@...il.com>, <snu@...zon.de>,
        <vbabka@...e.cz>, <vdavydov.dev@...il.com>,
        <yang.shi@...ux.alibaba.com>, <ying.huang@...el.com>,
        <linux-damon@...zon.com>, <linux-mm@...ck.org>,
        <linux-doc@...r.kernel.org>, <linux-kernel@...r.kernel.org>
Subject: Re: Re: [PATCH v13 05/15] mm/damon: Adaptively adjust regions

On Wed, 27 May 2020 13:23:56 +0200 Leonard Foerster <foersleo@...zon.com> wrote:

> On 2020-05-25T11:15:02+02:00 SeongJae Park <sjpark@...zon.com> wrote:
> 
> > From: SeongJae Park <sjpark@...zon.de>
> > 
> > At the beginning of the monitoring, DAMON constructs the initial regions
> > by evenly splitting the memory mapped address space of the process into
> > the user-specified minimal number of regions.  In this initial state,
> > the assumption of the regions (pages in same region have similar access
> > frequencies) is normally not kept and thus the monitoring quality could
> > be low.  To keep the assumption as much as possible, DAMON adaptively
> > merges and splits each region.
> > 
> > For each ``aggregation interval``, it compares the access frequencies of
> > adjacent regions and merges those if the frequency difference is small.
> > Then, after it reports and clears the aggregated access frequency of
> > each region, it splits each region into two regions if the total number
> > of regions is smaller than the half of the user-specified maximum number
> > of regions.
> > 
> > In this way, DAMON provides its best-effort quality and minimal overhead
> > while keeping the bounds users set for their trade-off.
> > 
> > Signed-off-by: SeongJae Park <sjpark@...zon.de>
> > ---
> > [...]
> > +/*
> > + * splits every target region into two randomly-sized regions
> > + *
> > + * This function splits every target region into two random-sized regions if
> > + * current total number of the regions is equal or smaller than half of the
> > + * user-specified maximum number of regions.  This is for maximizing the
> > + * monitoring accuracy under the dynamically changeable access patterns.  If a
> > + * split was unnecessarily made, later 'kdamond_merge_regions()' will revert
> > + * it.
> > + */
> > +static void kdamond_split_regions(struct damon_ctx *ctx)
> > +{
> > +	struct damon_task *t;
> > +	unsigned int nr_regions = 0;
> > +	static unsigned int last_nr_regions;
> > +	int nr_subregions = 2;
> > +
> > +	damon_for_each_task(t, ctx)
> > +		nr_regions += nr_damon_regions(t);
> > +
> > +	if (nr_regions > ctx->max_nr_regions / 2)
> > +		return;
> > +
> > +	/* If number of regions is not changed, we are maybe in corner case */
> > +	if (last_nr_regions == nr_regions &&
> > +			nr_regions < ctx->max_nr_regions / 3)
> > +		nr_subregions = 3;
> > +
> > +	damon_for_each_task(t, ctx)
> > +		damon_split_regions_of(ctx, t, nr_subregions);
> > +
> > +	if (!last_nr_regions)
> > +		last_nr_regions = nr_regions;
> 
> So we are only setting last_nr_regions once when we first come along
> here (when last_nr_regions == 0). Thus we are checking from now on if
> nr_regions is the same as nr_regions was before the first ever split. So
> we are doing the three-way split whenever nr_regions has come to the
> initial number of regions. Is this actually what we want? The naming
> suggests that we want to check against the number before the last split
> to detect if we have moved into a spot where we are splitting and
> merging back and forth between two states (this is the corner case we
> are talking about?).
> 
> Or am I misunderstanding the intention here?

Oops, you're right, I made obvious mistake.  Thank you for finding this.  I
will fix this in the next spin.


Thanks,
SeongJae Park

> 
> Leonard