From patchwork Fri Sep 15 02:52:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 13386314 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 072B2EE0205 for ; Fri, 15 Sep 2023 02:53:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 747F76B02F2; Thu, 14 Sep 2023 22:53:08 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6F7566B030C; Thu, 14 Sep 2023 22:53:08 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 597F66B030D; Thu, 14 Sep 2023 22:53:08 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 457266B02F2 for ; Thu, 14 Sep 2023 22:53:08 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 0E333B42B0 for ; Fri, 15 Sep 2023 02:53:08 +0000 (UTC) X-FDA: 81237310056.18.B8EE4F2 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf20.hostedemail.com (Postfix) with ESMTP id 52D3F1C000F for ; Fri, 15 Sep 2023 02:53:06 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=pq35bGOV; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf20.hostedemail.com: domain of sj@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=sj@kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1694746386; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=TR+0ywkwjASKLQUKEDWUDGl5u35ACwoap9KEj50pecQ=; b=hkafpnxNxoj3F+B6dQ/isCle1oFyDtKDYY3YTlAtOfCFyiWBvjX9aO6sJGbPY9OZb8U/H/ uv7YyoGYWqk058Id5umGkwhwkkjE+5x2KK03Am6Ni15OVunIolCSgcrgiCzIqgT/lSMky6 ulK2rW5tqdBCRwSzq8h0Zykc0cVQW+s= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=pq35bGOV; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf20.hostedemail.com: domain of sj@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=sj@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694746386; a=rsa-sha256; cv=none; b=MtaAx2GoYKzKrOUP8VMvduWj3sFUs9INiDBEdFWJiqL4eOQ+Ju5RXLJOXdszkjSeLTwoR/ LlDsAOzlGok/1Cvp1LEL1tbZZ3IFVHd0zW8rycztIyiWa+UimziqpT3AUvSrluf8T+IpUF OUh76SI3ovDAP7z9f+vyyfhNwAxBRsY= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 9102061EE5; Fri, 15 Sep 2023 02:53:05 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id EF5EEC433C9; Fri, 15 Sep 2023 02:53:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1694746385; bh=1bmqeGHeOEZ2+59SSNfs3s06RBUS+Jm7Zbyglu1mAv8=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=pq35bGOVZLCqwdN44XaOtHhtXWKjJs4HFDnB6LU85Y8bqJGxt1jDLEDCJU2EyKY+O YX5rUFZ2j1WYGzXpnC7MZBLFG2mDmvZeEfZdKl41qov99fPrnnqoh+cNnRDJkUYL3p rFdgb+uAr4opnrxmKSWOZexjjdsFRCkMkgrfNixVpJCRtruxa93AEdCyE1NRTx291T ro0iKYQKhKzXv3roZ+Ja5LGJ073h+DG/Vps8OkaCtQV1TNatAvCkVTNcX7c/2nEbsz hABBbXn7jgj5tI+nARlpwXKPSnM88OeQJWahUNlym4aIYY5r7PefSlPgceGMj0AeCt I0BpGP+LqEcKA== From: SeongJae Park To: Andrew Morton Cc: SeongJae Park , damon@lists.linux.dev, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 3/8] mm/damon/core: implement a pseudo-moving sum function Date: Fri, 15 Sep 2023 02:52:46 +0000 Message-Id: <20230915025251.72816-4-sj@kernel.org> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20230915025251.72816-1-sj@kernel.org> References: <20230915025251.72816-1-sj@kernel.org> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 52D3F1C000F X-Stat-Signature: 78prb8b4w4eewcmc4c5qmwi3zdfg97ts X-HE-Tag: 1694746386-815605 X-HE-Meta: U2FsdGVkX1+KvjefMS+0AevalqYYjUp52yZLqWms7QeHTIu5lef8yuzXhPGDAExySjl/eCYQYMadzXGkJI3o+f+1x+KK5Mdv5BEA00+09h1SWQq6yDNJKU8yU3GSBlHzMe1FyziHSCogurfVwj12EG5jC2MBz5hac+8QSmWzItSYP5QAy5X4xVAQq879ekemtiqiGqlpkhp/j2B9J/p7tb5dOS7rmEJ3aPMEibtu+A5hT8RRriM80+EsVPqCDnt17fqHVvXvwNsD3hX6WOEeWWS6kgbfc3bRLDQwdM9OcDuuMvDYBaW+ReQdxviabzg+VSOL/ObKYqtdKVRSMTdIz7rOdJ9bE6jVfZRAwHuZnt9KaTr5YZtqM+JBn1RO8U8uS3rsZS0Ue93ooyoTUtRZmoV66F7Yif4iiVzP7q4IYUNO2oEzlPXepSQcPyC0g6G6ItGAU+tHsvIbmieGfVK8Ntnxs1pIDcOwLSZe42Dx2nREAB9k7pNNdAIctfM0TS1VKfTwy8+aioyS1ZuXVRVWGfhBjf0cbGaW/6XQHSfFN0U0TbX30MXsqONyhGc0zcYEbMpEMOznWW/wYQMhlj5WfdELGCR9zTApCojDZiovhEuYZi64b2/u/Xz6ZsJWxwUOj79knrLvJHaMkmvpSFCCtffxx3Gg69f/zAbWN/FslmLIGVsQW884fZ1MJiTORju2nwNLf7R62anNWxtwhU6qy0fzOZaGVFwYI6PiNS3IspN1DkyH+kS/1suROsHctWsoPgBP7zY7uyi+0vxoo+8g0LXwWlajoLgTELmfFZ/nBD1tNvvYug/k2KPl+8qEe98phf7GoURuVBV7cNFvYXNLRBTmvbY5GkTnvMyT5S2uG5+b/1MVfhV8EYpX3sPG3Jsp8VXA4KY2PEjgf7fE/DIX5caufr1uNIuJjVPMYL11fVEtVuS/41Y91AV7yABTNN8aDACG0D//eGcY36J0tf6 Y2g/UxG+ IwBXSSjUJFGMLt878+Pz3mzy3Y2DbM8Vhj+hPEAI/5AXIvRu2htyGoVDx5Qep875Bnortx4scGwrC3l3KkSWSBCMjOaznd83wwvWmo59lGyBglmGDnfDTfQvLYX3YO2abgWUg5zhFG+FvuPRS/uVV1y5KNK91tlY9QzjAet80YfGKwp68kwd4OGpD/Ria29YrbtAaW12JlSG8cHLrvumit88g4YD8OFEdQLeAkiySRpHl8Sy2D/Udcd2Cr8nZKKzvCWubygyAPYx+xFgUokRk374J08PDYr7RbkmsbniwASZFqbxh2rzb8U/7seLuH8Sy5lP2Bgwv/gH/Dz8TdsrJlWNNqQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000018, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: For values that continuously change, moving average or sum are good ways to provide fast updates while handling temporal and errorneous variability of the value. For example, the access rate counter (nr_accesses) is calculated as a sum of the number of positive sampled access check results that collected during a discrete time window (aggregation interval), and hence it handles temporal and errorneous access check results, but provides the update only for every aggregation interval. Using a moving sum method for that could allow providing the value for every sampling interval. That could be useful for getting monitoring results snapshot or running DAMOS in fine-grained timing. However, supporting the moving sum for cases that number of samples in the time window is arbirary could impose high overhead, since the number of past values that it needs to keep could be too high. The nr_accesses would also be one of the cases. To mitigate the overhead, implement a pseudo-moving sum function that only provides an estimated pseudo-moving sum. It assumes there was no error in last discrete time window and subtract constant portion of last discrete time window sum. Note that the function is not strictly implementing the moving sum, but it keeps a property of moving sum, which makes the value same to the dsicrete-window based sum for each time window-aligned timing. Hence, people collecting the value in the old timings would show no difference. Signed-off-by: SeongJae Park --- include/linux/damon.h | 2 ++ mm/damon/core.c | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 42 insertions(+) diff --git a/include/linux/damon.h b/include/linux/damon.h index 17c504d236b9..487a545a11b4 100644 --- a/include/linux/damon.h +++ b/include/linux/damon.h @@ -622,6 +622,8 @@ void damon_add_region(struct damon_region *r, struct damon_target *t); void damon_destroy_region(struct damon_region *r, struct damon_target *t); int damon_set_regions(struct damon_target *t, struct damon_addr_range *ranges, unsigned int nr_ranges); +unsigned int damon_moving_sum(unsigned int mvsum, unsigned int nomvsum, + unsigned int len_window, unsigned int new_value); void damon_update_region_access_rate(struct damon_region *r, bool accessed); struct damos_filter *damos_new_filter(enum damos_filter_type type, diff --git a/mm/damon/core.c b/mm/damon/core.c index 10532159323a..b005dc15009f 100644 --- a/mm/damon/core.c +++ b/mm/damon/core.c @@ -1549,6 +1549,46 @@ int damon_set_region_biggest_system_ram_default(struct damon_target *t, return damon_set_regions(t, &addr_range, 1); } +/* + * damon_moving_sum() - Calculate an inferred moving sum value. + * @mvsum: Inferred sum of the last @len_window values. + * @nomvsum: Non-moving sum of the last discrete @len_window window values. + * @len_window: The number of last values to take care of. + * @new_value: New value that will be added to the pseudo moving sum. + * + * Moving sum (moving average * window size) is good for handling noise, but + * the cost of keeping past values can be high for arbitrary window size. This + * function implements a lightweight pseudo moving sum function that doesn't + * keep the past window values. + * + * It simply assumes there was no noise in the past, and get the no-noise + * assumed past value to drop from @nomvsum and @len_window. @nomvsum is a + * non-moving sum of the last window. For example, if @len_window is 10 and we + * have 25 values, @nomvsum is the sum of the 11th to 20th values of the 25 + * values. Hence, this function simply drops @nomvsum / @len_window from + * given @mvsum and add @new_value. + * + * For example, if @len_window is 10 and @nomvsum is 50, the last 10 values for + * the last window could be vary, e.g., 0, 10, 0, 10, 0, 10, 0, 0, 0, 20. For + * calculating next moving sum with a new value, we should drop 0 from 50 and + * add the new value. However, this function assumes it got value 5 for each + * of the last ten times. Based on the assumption, when the next value is + * measured, it drops the assumed past value, 5 from the current sum, and add + * the new value to get the updated pseduo-moving average. + * + * This means the value could have errors, but the errors will be disappeared + * for every @len_window aligned calls. For example, if @len_window is 10, the + * pseudo moving sum with 11th value to 19th value would have an error. But + * the sum with 20th value will not have the error. + * + * Return: Pseudo-moving average after getting the @new_value. + */ +unsigned int damon_moving_sum(unsigned int mvsum, unsigned int nomvsum, + unsigned int len_window, unsigned int new_value) +{ + return mvsum - nomvsum / len_window + new_value; +} + /** * damon_update_region_access_rate() - Update the access rate of a region. * @r: The DAMON region to update for its access check result.