From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 72C76C47083 for ; Mon, 31 May 2021 13:38:42 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 1DA886195A for ; Mon, 31 May 2021 13:38:42 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 1DA886195A Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id B3F7E6B0078; Mon, 31 May 2021 09:38:41 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B18066B007B; Mon, 31 May 2021 09:38:41 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 942608D0002; Mon, 31 May 2021 09:38:41 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0135.hostedemail.com [216.40.44.135]) by kanga.kvack.org (Postfix) with ESMTP id 6345F6B0078 for ; Mon, 31 May 2021 09:38:41 -0400 (EDT) Received: from smtpin16.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 0B18A18018A1F for ; Mon, 31 May 2021 13:38:41 +0000 (UTC) X-FDA: 78201631242.16.825AF2E Received: from mail-qk1-f178.google.com (mail-qk1-f178.google.com [209.85.222.178]) by imf20.hostedemail.com (Postfix) with ESMTP id D036942D for ; Mon, 31 May 2021 13:38:25 +0000 (UTC) Received: by mail-qk1-f178.google.com with SMTP id 124so11172233qkh.10 for ; Mon, 31 May 2021 06:38:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=rPT2C202JOCkRiKiiUXRjRL23w8b5eMtZrrbe+b900k=; b=cLAGoywmSTv3PD8nM0E7Gqmr/BryPNiuCCMVBaqgtmXD+2+i/diYXoA7prqMYlaxJu h47Tu0JIuzTuigXwwsbLdxMNEYA9XnGqRZaA7OJM5pjImRrXobcfq1VAmOc6HsB9w0cP p6nYVr19pIE3ATccFi6tJJpopMtiB9MTl4ty21N7VnOasrlF7rZGgTH8MnVKnPrGKWAV jklSdD1t0aVLJrBQ0K4oF01ya+yqVg1FHkci4xoPx4jxdgi22nJ46kzFKKPqRyw+TtxK dToU1fxOb8/OGu54kdutvLfzNNqqHcAsPT+M4doFbKt0x7UAV5jxRTBB3NakTPnC+bem 9u+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=rPT2C202JOCkRiKiiUXRjRL23w8b5eMtZrrbe+b900k=; b=f2KRJyQE70w8dRXa72ZjpxXg2sb1T0LkY6iFcHtOFs94Lec8FIJfxozUHWx1+ihBuB 6RXu6Lxd73PTXFUR2uLh8vmZk0QlZyo0qyyuu2rDaJ2a9Z9s12JHx3Fq4ArQroLwObGa m3esO4bq508Erh7ZAoM97mYXny3Eh5ktYmMWUTr7wZvidU8JdnmajhBhCcugd+HuXbZN qRUE+80DIvUhGgz209yAAQqSUOmEC7oIT5y4X9bvjWcT0iT98DWnX//264YSDbChpaXY OX6HP8wsNWvcatRZO/qc+RuFbU3KWtkizS1GpE+ELeBP8XD/05MyWfQQCgECsRRs5SRt RXFg== X-Gm-Message-State: AOAM5315YYZVun0t6IhHCm8oHg38MPB+GwuYujcM3vRKyJnk/U33QqZ9 SeBy9j7iFDj11KSSeOosvb4= X-Google-Smtp-Source: ABdhPJzdiuMFvJ0hWzobTa/oxU0rbSmJ3QTa8/QvzAEZQG1ZQBQPnrokd0QaHrR/7W5TmrSl5GPW8w== X-Received: by 2002:a05:620a:15ca:: with SMTP id o10mr16956713qkm.448.1622468320086; Mon, 31 May 2021 06:38:40 -0700 (PDT) Received: from localhost.localdomain (ec2-35-169-212-159.compute-1.amazonaws.com. [35.169.212.159]) by smtp.gmail.com with ESMTPSA id h8sm8293085qtp.46.2021.05.31.06.38.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 31 May 2021 06:38:39 -0700 (PDT) From: sj38.park@gmail.com To: akpm@linux-foundation.org Cc: SeongJae Park , Jonathan.Cameron@Huawei.com, acme@kernel.org, alexander.shishkin@linux.intel.com, amit@kernel.org, benh@kernel.crashing.org, brendanhiggins@google.com, corbet@lwn.net, david@redhat.com, dwmw@amazon.com, elver@google.com, fan.du@intel.com, foersleo@amazon.de, greg@kroah.com, gthelen@google.com, guoju.fgj@alibaba-inc.com, mgorman@suse.de, minchan@kernel.org, mingo@redhat.com, namhyung@kernel.org, peterz@infradead.org, riel@surriel.com, rientjes@google.com, rostedt@goodmis.org, rppt@kernel.org, shakeelb@google.com, shuah@kernel.org, sj38.park@gmail.com, snu@zelle79.org, vbabka@suse.cz, vdavydov.dev@gmail.com, zgf574564920@gmail.com, linux-damon@amazon.com, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [RFC PATCH 06/13] mm/damon/schemes: Prioritize regions within speed limit Date: Mon, 31 May 2021 13:38:09 +0000 Message-Id: <20210531133816.12689-7-sj38.park@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20210531133816.12689-1-sj38.park@gmail.com> References: <20210531133816.12689-1-sj38.park@gmail.com> Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20161025 header.b=cLAGoywm; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf20.hostedemail.com: domain of sj38park@gmail.com designates 209.85.222.178 as permitted sender) smtp.mailfrom=sj38park@gmail.com X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: D036942D X-Stat-Signature: x5zkkntayim9rioxrh9nrxycrdfkdxw7 X-HE-Tag: 1622468305-76141 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: From: SeongJae Park This commit makes DAMON to apply schemes to regions having higher priority first, if it cannot apply schemes to all regions due to the speed limit. The prioritization function should be implemented in each monitoring primitive. Those would commonly calculate the priority of the region using attributes of regions, namely 'size', 'nr_accesses', and 'age'. For example, some primitive would calculate the priority of each region using a weighted sum of 'nr_accesses' and 'age' of the region. The optimal weights would depend on give environments, so this commit allows it to be customizable. Nevertheless, the score calculation functions are only encouraged to respect the weights, not mandated. So, the customization might not work for some primitives. Signed-off-by: SeongJae Park --- include/linux/damon.h | 27 ++++++++++++++++- mm/damon/core.c | 70 ++++++++++++++++++++++++++++++++++++------- 2 files changed, 86 insertions(+), 11 deletions(-) diff --git a/include/linux/damon.h b/include/linux/damon.h index 0df81dd2d560..8f35bd94fc2b 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -14,6 +14,8 @@ /* Minimal region size. Every damon_region is aligned by this. */ #define DAMON_MIN_REGION PAGE_SIZE +/* Max priority score for DAMON-based operation schemes */ +#define DAMOS_MAX_SCORE (99) /** * struct damon_addr_range - Represents an address region of [@start, @end). @@ -92,8 +94,18 @@ enum damos_action { * @sz: Scheme action amount limit in bytes. * @ms: Scheme action amount charge duration. * + * @weight_sz: Weight of the region's size for prioritization. + * @weight_nr_accesses: Weight of the region's nr_accesses for prioritization. + * @weight_age: Weight of the region's age for prioritization. + * * To avoid consuming too much CPU time for applying the &struct damos->action - * to large memory, DAMON applies it to only up to &sz bytes within &ms. + * to large memory, DAMON applies it to only up to &sz bytes within &ms. For + * selecting regions within the limit, DAMON prioritizes current scheme's + * target memory regions using the given &struct + * damon_primitive->get_scheme_score. You could customize the prioritization + * logic for your environment by setting &weight_sz, &weight_nr_accesses, and + * &weight_age, because primitives are encouraged to respect those, though it's + * not mandatory. * * If &sz is 0, the limit is disabled. */ @@ -101,11 +113,18 @@ struct damos_speed_limit { unsigned long sz; unsigned long ms; + unsigned int weight_sz; + unsigned int weight_nr_accesses; + unsigned int weight_age; + /* private: for limit accounting */ unsigned long charged_sz; unsigned long charged_from; struct damon_target *charge_target_from; unsigned long charge_addr_from; + + unsigned long histogram[DAMOS_MAX_SCORE + 1]; + unsigned int min_score; }; /** @@ -155,6 +174,7 @@ struct damon_ctx; * @prepare_access_checks: Prepare next access check of target regions. * @check_accesses: Check the accesses to target regions. * @reset_aggregated: Reset aggregated accesses monitoring results. + * @get_scheme_score: Get the score of a region for a scheme. * @apply_scheme: Apply a DAMON-based operation scheme. * @target_valid: Determine if the target is valid. * @cleanup: Clean up the context. @@ -182,6 +202,8 @@ struct damon_ctx; * of its update. The value will be used for regions adjustment threshold. * @reset_aggregated should reset the access monitoring results that aggregated * by @check_accesses. + * @get_scheme_score should return the priority score of a region for a scheme + * as an integer in [0, &DAMOS_MAX_SCORE]. * @apply_scheme is called from @kdamond when a region for user provided * DAMON-based operation scheme is found. It should apply the scheme's action * to the region. This is not used for &DAMON_ARBITRARY_TARGET case. @@ -196,6 +218,9 @@ struct damon_primitive { void (*prepare_access_checks)(struct damon_ctx *context); unsigned int (*check_accesses)(struct damon_ctx *context); void (*reset_aggregated)(struct damon_ctx *context); + int (*get_scheme_score)(struct damon_ctx *context, + struct damon_target *t, struct damon_region *r, + struct damos *scheme); int (*apply_scheme)(struct damon_ctx *context, struct damon_target *t, struct damon_region *r, struct damos *scheme); bool (*target_valid)(void *target); diff --git a/mm/damon/core.c b/mm/damon/core.c index fab687f18d9c..15bcd05670d1 100644 --- a/mm/damon/core.c +++ b/mm/damon/core.c @@ -12,6 +12,7 @@ #include #include #include +#include #define CREATE_TRACE_POINTS #include @@ -105,11 +106,13 @@ struct damos *damon_new_scheme( scheme->limit.sz = limit->sz; scheme->limit.ms = limit->ms; + scheme->limit.weight_sz = limit->weight_sz; + scheme->limit.weight_nr_accesses = limit->weight_nr_accesses; + scheme->limit.weight_age = limit->weight_age; scheme->limit.charged_sz = 0; scheme->limit.charged_from = 0; scheme->limit.charge_target_from = NULL; scheme->limit.charge_addr_from = 0; - return scheme; } @@ -546,6 +549,28 @@ static void kdamond_reset_aggregated(struct damon_ctx *c) static void damon_split_region_at(struct damon_ctx *ctx, struct damon_region *r, unsigned long sz_r); +static bool __damos_valid_target(struct damon_region *r, struct damos *s) +{ + unsigned long sz; + + sz = r->ar.end - r->ar.start; + return s->min_sz_region <= sz && sz <= s->max_sz_region && + s->min_nr_accesses <= r->nr_accesses && + r->nr_accesses <= s->max_nr_accesses && + s->min_age_region <= r->age && r->age <= s->max_age_region; +} + +static bool damos_valid_target(struct damon_ctx *c, struct damon_target *t, + struct damon_region *r, struct damos *s) +{ + bool ret = __damos_valid_target(r, s); + + if (!ret || !s->limit.sz || !c->primitive.get_scheme_score) + return ret; + + return c->primitive.get_scheme_score(c, t, r, s) >= s->limit.min_score; +} + static void damon_do_apply_schemes(struct damon_ctx *c, struct damon_target *t, struct damon_region *r) @@ -575,17 +600,11 @@ static void damon_do_apply_schemes(struct damon_ctx *c, limit->charge_addr_from = 0; } - sz = r->ar.end - r->ar.start; - /* Check the target regions condition */ - if (sz < s->min_sz_region || s->max_sz_region < sz) - continue; - if (r->nr_accesses < s->min_nr_accesses || - s->max_nr_accesses < r->nr_accesses) - continue; - if (r->age < s->min_age_region || s->max_age_region < r->age) + if (!damos_valid_target(c, t, r, s)) continue; /* Apply the scheme */ + sz = r->ar.end - r->ar.start; if (c->primitive.apply_scheme) { if (limit->sz && limit->charged_sz + sz > limit->sz) { sz = limit->sz - limit->charged_sz; @@ -615,13 +634,44 @@ static void kdamond_apply_schemes(struct damon_ctx *c) damon_for_each_scheme(s, c) { struct damos_speed_limit *limit = &s->limit; + unsigned long cumulated_sz; + unsigned int score, max_score = 0; + + if (!limit->sz) + continue; /* Reset charge window if the duration passed */ - if (limit->sz && time_after_eq(jiffies, s->limit.charged_from + + if (time_after_eq(jiffies, s->limit.charged_from + msecs_to_jiffies(s->limit.ms))) { limit->charged_from = jiffies; limit->charged_sz = 0; } + + if (!c->primitive.get_scheme_score) + continue; + + /* Fill up the score histogram */ + memset(limit->histogram, 0, sizeof(limit->histogram)); + damon_for_each_target(t, c) { + damon_for_each_region(r, t) { + if (!__damos_valid_target(r, s)) + continue; + score = c->primitive.get_scheme_score( + c, t, r, s); + limit->histogram[score] += + r->ar.end - r->ar.start; + if (score > max_score) + max_score = score; + } + } + + /* Set the min score limit */ + for (cumulated_sz = 0, score = max_score; ; score--) { + cumulated_sz += limit->histogram[score]; + if (cumulated_sz >= limit->sz || !score) + break; + } + limit->min_score = score; } damon_for_each_target(t, c) { -- 2.17.1