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.8 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 5C7A8C47082 for ; Tue, 8 Jun 2021 11:53:27 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 0F50E6128D for ; Tue, 8 Jun 2021 11:53:27 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 0F50E6128D 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 A86A36B0074; Tue, 8 Jun 2021 07:53:26 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A60E16B0075; Tue, 8 Jun 2021 07:53:26 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8134B6B0078; Tue, 8 Jun 2021 07:53:26 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0226.hostedemail.com [216.40.44.226]) by kanga.kvack.org (Postfix) with ESMTP id 4F2A76B0074 for ; Tue, 8 Jun 2021 07:53:26 -0400 (EDT) Received: from smtpin34.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id F12739898 for ; Tue, 8 Jun 2021 11:53:25 +0000 (UTC) X-FDA: 78230396370.34.61EEC52 Received: from mail-qv1-f42.google.com (mail-qv1-f42.google.com [209.85.219.42]) by imf11.hostedemail.com (Postfix) with ESMTP id 3A33020010AA for ; Tue, 8 Jun 2021 11:53:22 +0000 (UTC) Received: by mail-qv1-f42.google.com with SMTP id u14so7675635qvq.6 for ; Tue, 08 Jun 2021 04:53:25 -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=USupWkjstKLzS9GL1eZ+AKXClsG/TjR98Rj/j8aN4z0=; b=Z/Knr8Fgp9bWjg1dd0BIpTKDEBXVpsMpZ3+elPatEnn5m801o33WnyZYHWQifpPT7H qc3aLzdcU3Ixq28wk30Reufga9vdRaLhMmwJr9S/5hNxWiW7iGy1KAjSA79sIjLqrtAX B1tkfsqUNz51ADga1t7fk9SvFgXMEcX8Wkr5LTDu/FO1xhh49lt3/OG/SyARRO+M2Csx QnkbGAPXhi/8QlDRjM0YjD161hlsCuIGipgB9jLv3mUnG+pd8rMjwWm2B/Fq7bf2EQFT kjkNLRD1IcJNIdWbJ8IO5SCc73zy0UWM9g8tx5d8wVDJuW3YboYrWHjGyd+PgybgvzE4 yf4w== 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=USupWkjstKLzS9GL1eZ+AKXClsG/TjR98Rj/j8aN4z0=; b=KySqRDX28pWRTI9+flC4tKW/d3vjwnw00tsi5FQiC2SOsCkA7HjpJ+3IIDcCcQ57wx CJ0JuiS4X65Uy9xdrqB4L5eBNP9MrgdYbW0BzuRvSYw/wQIU6U8XfY28GcPEyk1xEDbw 5mVzVMgMf0MuOK06YVI6RcOqiLZ6bMV8bWCpfe4RvellF+kIPPolq55XRrLRrDYJfu66 MrGgczPKO1x+RHgUExWMFGc0Q4AQR218Gi2+mKNLegDu0UggjrDFI4cFKBufivpWys+5 hHVMQYanSwePmcsugdiVqFOfP5g923vFRdnWZy3Aj0rVFGjxFzkn5sc3UHaU6GAwCrGq w06g== X-Gm-Message-State: AOAM530GVbPjf09hAfalpKbbN4GvsE0y9C5SMluUjEL1163AKL4fGe21 LQl9VoyLdS0fnhkAmNL4Fbk= X-Google-Smtp-Source: ABdhPJziaxjKD2gnNPTzevzkb3cN3YS/ADUNou87xRED4m+fbEP2mh4YVLkGZXxtdWHNNE0qodFlTQ== X-Received: by 2002:a0c:e185:: with SMTP id p5mr22740331qvl.17.1623153205024; Tue, 08 Jun 2021 04:53:25 -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 h4sm2133927qth.66.2021.06.08.04.53.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Jun 2021 04:53:24 -0700 (PDT) From: SeongJae Park 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, jgowans@amazon.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 v2 06/14] mm/damon/schemes: Prioritize regions within speed limit Date: Tue, 8 Jun 2021 11:52:46 +0000 Message-Id: <20210608115254.11930-7-sj38.park@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20210608115254.11930-1-sj38.park@gmail.com> References: <20210608115254.11930-1-sj38.park@gmail.com> X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 3A33020010AA Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20161025 header.b="Z/Knr8Fg"; spf=pass (imf11.hostedemail.com: domain of sj38park@gmail.com designates 209.85.219.42 as permitted sender) smtp.mailfrom=sj38park@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-Stat-Signature: 1jeiaggyqy3i9gjsmp3azuun8yyzfzjn X-HE-Tag: 1623153202-604081 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 | 69 ++++++++++++++++++++++++++++++++++++------- 2 files changed, 84 insertions(+), 12 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 5864b63c18f9..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,16 +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 (time_after_eq(jiffies, limit->charged_from + - msecs_to_jiffies(limit->ms))) { + 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