Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
IronPort-SDR: bD3UbNFmyebn4uwq18PQt0i8oiWF+RXahclxjzXJksOdvJkbbH5fFLifCG5di9rzz3zM8c6HQk
 dpxbU9ZLF78w==
From:   SeongJae Park <sjpark@amazon.com>
To:     <akpm@linux-foundation.org>
CC:     SeongJae Park <sjpark@amazon.de>, <Jonathan.Cameron@Huawei.com>,
        <aarcange@redhat.com>, <acme@kernel.org>,
        <alexander.shishkin@linux.intel.com>, <amit@kernel.org>,
        <benh@kernel.crashing.org>, <brendan.d.gregg@gmail.com>,
        <brendanhiggins@google.com>, <cai@lca.pw>,
        <colin.king@canonical.com>, <corbet@lwn.net>, <dwmw@amazon.com>,
        <irogers@google.com>, <jolsa@redhat.com>, <kirill@shutemov.name>,
        <mark.rutland@arm.com>, <mgorman@suse.de>, <minchan@kernel.org>,
        <mingo@redhat.com>, <namhyung@kernel.org>, <peterz@infradead.org>,
        <rdunlap@infradead.org>, <riel@surriel.com>, <rientjes@google.com>,
        <rostedt@goodmis.org>, <sblbir@amazon.com>, <shakeelb@google.com>,
        <shuah@kernel.org>, <sj38.park@gmail.com>, <snu@amazon.de>,
        <vbabka@suse.cz>, <vdavydov.dev@gmail.com>,
        <yang.shi@linux.alibaba.com>, <ying.huang@intel.com>,
        <linux-damon@amazon.com>, <linux-mm@kvack.org>,
        <linux-doc@vger.kernel.org>, <linux-kernel@vger.kernel.org>
Subject: [PATCH v11 06/16] mm/damon: Split regions into 3 subregions if necessary
Date:   Mon, 11 May 2020 14:32:52 +0200
Message-ID: <20200511123302.12520-7-sjpark@amazon.com>
In-Reply-To: <20200511123302.12520-1-sjpark@amazon.com>
References: <20200511123302.12520-1-sjpark@amazon.com>
MIME-Version: 1.0
Content-Type: text/plain
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

From: SeongJae Park <sjpark@amazon.de>

Suppose that there are a very wide and cold region and a hot region, and
both regions are identified by DAMON.  And then, the middle small region
inside the very wide and cold region becomes hot.  DAMON will not be
able to identify this new region because the adaptive regions adjustment
mechanism splits each region to only two subregions.

This commit modifies the logic to split each region to 3 subregions if
such corner case is detected.

Suggested-by: James Cameron <Jonathan.Cameron@Huawei.com>
Signed-off-by: SeongJae Park <sjpark@amazon.de>
---
 mm/damon.c | 51 ++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 34 insertions(+), 17 deletions(-)

diff --git a/mm/damon.c b/mm/damon.c
index cec946197e13..fbf37df841ce 100644
--- a/mm/damon.c
+++ b/mm/damon.c
@@ -650,26 +650,32 @@ static void damon_split_region_at(struct damon_ctx *ctx,
 	damon_insert_region(new, r, damon_next_region(r));
 }
 
-/* Split every region in the given task into two randomly-sized regions */
-static void damon_split_regions_of(struct damon_ctx *ctx, struct damon_task *t)
+/* Split every region in the given task into 'nr_subs' regions */
+static void damon_split_regions_of(struct damon_ctx *ctx,
+				     struct damon_task *t, int nr_subs)
 {
 	struct damon_region *r, *next;
-	unsigned long sz_orig_region, sz_left_region;
+	unsigned long sz_region, sz_sub = 0;
+	int i;
 
 	damon_for_each_region_safe(r, next, t) {
-		sz_orig_region = r->vm_end - r->vm_start;
-
-		/*
-		 * Randomly select size of left sub-region to be at least
-		 * 10 percent and at most 90% of original region
-		 */
-		sz_left_region = ALIGN_DOWN(damon_rand(1, 10) * sz_orig_region
-					    / 10, MIN_REGION);
-		/* Do not allow blank region */
-		if (sz_left_region == 0 || sz_left_region >= sz_orig_region)
-			continue;
-
-		damon_split_region_at(ctx, r, sz_left_region);
+		sz_region = r->vm_end - r->vm_start;
+
+		for (i = 0; i < nr_subs - 1 &&
+				sz_region > 2 * MIN_REGION; i++) {
+			/*
+			 * Randomly select size of left sub-region to be at
+			 * least 10 percent and at most 90% of original region
+			 */
+			sz_sub = ALIGN_DOWN(damon_rand(1, 10) *
+					sz_region / 10, MIN_REGION);
+			/* Do not allow blank region */
+			if (sz_sub == 0 || sz_sub >= sz_region)
+				continue;
+
+			damon_split_region_at(ctx, r, sz_sub);
+			sz_region = sz_sub;
+		}
 	}
 }
 
@@ -687,14 +693,25 @@ 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(ctx, t)
 		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(ctx, t)
-		damon_split_regions_of(ctx, t);
+		damon_split_regions_of(ctx, t, nr_subregions);
+
+	if (!last_nr_regions)
+		last_nr_regions = nr_regions;
 }
 
 /*
-- 
2.17.1