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 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 122FAEEB581 for ; Sat, 9 Sep 2023 03:37:28 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CFAFE6B00F6; Fri, 8 Sep 2023 23:37:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CAA5F6B00F8; Fri, 8 Sep 2023 23:37:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B9B376B00FE; Fri, 8 Sep 2023 23:37:27 -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 AA9076B00F6 for ; Fri, 8 Sep 2023 23:37:27 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 5894F1602D9 for ; Sat, 9 Sep 2023 03:37:27 +0000 (UTC) X-FDA: 81215648934.27.F0B514C Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf28.hostedemail.com (Postfix) with ESMTP id B1C9AC0016 for ; Sat, 9 Sep 2023 03:37:25 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=M217PYuf; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf28.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=1694230645; 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:references:dkim-signature; bh=btjdeY2CwDBT9/jfs5VJiSxO0bAtJ9mCzJyCndhZojA=; b=fdsFYoCctRr3BuqapFcL6h5miuGQriE2SAykf885JGopJ6HIqmt17ZHNnl+2HWn63xKvC8 kcI+WyGxY3AZGMguhjl7tGjqtYTXTBhxb9/P+mTnQC3+XWshxLmKMbd3uQxXzOOqmGhBUN DOIpjH7B7KaR1Y88P8k1l/B7XjIRtNM= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=M217PYuf; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf28.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=1694230645; a=rsa-sha256; cv=none; b=0nV1oqCftBSmxNMdpoiEKI8iqSVbGjEKTMXNo9aNuCAUgL9Zvk+4YtLCnOQGHsIJkx1gsH Zj5RyKOZvP2bad/67BvRx09WJMEWEqFEoc2QX5yFtKuYoOi5Bq8tqvfwyDDSVc+h7KVdGo vchRkmMi7rh9pqLOhB7kkDmZN4O8laU= 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 B46BE6140B; Sat, 9 Sep 2023 03:37:24 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 81EC0C433C8; Sat, 9 Sep 2023 03:37:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1694230644; bh=LIdwZZs4OlFQUm7n2Pdv3lOWj7cVGyn8OJFVzIV68m4=; h=From:To:Cc:Subject:Date:From; b=M217PYuf/bogc6R0vAiF1bc6bzDfX7fBWV8BUUZIgvFS2WdG2nAz13yIdyZBxH6Zn sDHTIBYWe2sFLGXzw9XTHq07+SW+W1Pp4kZGB57RnI/f5fFhFdfj0LH4w/sjm02n0f qxPax/8dCCDs29wze4VUlS9dzaQJ50F5Pt3rvMNkmEtRI2TCzMy/ICtYaly3e/qt29 d8v2mXzHReXp+F5NF5xqipvczSsxweLePWAnEbPj/sRUfHu981VgU1gxYxWyIPQNSk 4GbDnApHjrnqvCLEvZnd45Y3J7FCAWAoJ0f2WbU4EXOMBqfj9cImDNSXQE6piOBdIk DarmMoUr0tDzQ== From: SeongJae Park To: Cc: SeongJae Park , Andrew Morton , Brendan Higgins , damon@lists.linux.dev, linux-mm@kvack.org, kunit-dev@googlegroups.com, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [RFC 0/8] mm/damon: provide pseudo-moving sum based access rate Date: Sat, 9 Sep 2023 03:37:03 +0000 Message-Id: <20230909033711.55794-1-sj@kernel.org> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: B1C9AC0016 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 3zs45y19q6xkdu5hn1gdkoiqfhggqs1h X-HE-Tag: 1694230645-802658 X-HE-Meta: U2FsdGVkX1+V1WlWr1pZArQ4uG7QoF7BsG++0q/Viv+kjmaiE1zx+wNwmXGNP74VFLYX9hmo419Af2z97l5OfY5PW7d5jRFew9jccFayOdA+XLp8z87d7jJ8Va1nGk9gi8F/ZvRobl1VXfQ1rJSfaE0gszhAJQckc0VBYcPmAL3+MNf66fcLMX+Tu19YE5HQ05lysLT3wXYsia2dibnHwO2lUCiys3hW4Ece0jsbE8jk0U7znFhMcvU+l395PINdWB6vSwK44MxpiCGjzejIP4LbGQWK6DjtNFdIsu3Wa04RB/4DwjsOQd8al6ZW3iUM9ZaECbgjkUxhBJCRf8SxfrtKRNU4FjOj/YxVji5IqFCkL607JNknjjqXc/B77tqEdzay3pUg7czjgLEUF9WRV7RV5kB7AkYkqrwi2QIlxzeKZaF709bhxVZYJMKzOJk1L9ORH1Gi6TDcQZALpXrwYdYZ9S3wayygvww69evLW0tWRj9ijl7mHeaq1mAKeEQDPvZRfauX8qUzFM4+N1gnPdzczWrjwBCMz3NuqY9W3PMkFlc0a4VxMHPXIoKMRt2xdbtAawlr3EQKGGWGyN6V0/Bxoeb3/viNtE+2JD28jiFTDMPAmLnBOe2gUmg4PeLRLrAQLVWl4knY0qk8PC5KTFruC1koiRm3+Kz0nPyHLcocTBqF8XcNA9Mt6LFCj3b9I4L0PhuonU2iDrKiG1X+F6RMBNL+PhZfnzbPulBNRTgovgOErTUWtiR2McLtLzuvSqmLjKE8FujxZKsyCRyNTUunyTyNNaEJxLP0MFCnJGOzfkmOh8ECA5+TNYVURKOaTWYJSRo/dzn6agPGv1ezqYnXFcIf47nr38q0xRrKTnqZFF3JEy4SteDFNFFLihUhCG2SQWBCIWgFIx/3q2U4gjQ7zCFQtUcyT+9e+kUdNcsfxVGf6bwjrY+Hs4dXeWwZckOZ5yUw0UwGmmaGQYw XcJY5Yse 2vGLkkHLLQFbjOYhSZreW3+Ws7E7pO5UUMIVODLlXAcKnAOSgTMCxgg3+EW9JsXrwnTLd0HSxNolz0C6x5mzyhIi4qkXCceOQO76rf9DB8DFF6QMP5TLL6c8wVg1OaI4JKOEhN7lQHa8GJO0fdCbmAPQGtVO1ipRH+rFd7BaBERj4bnTQ/cc33F9Y44YvvUHpcB7rktobQ6+gTkUcnMaRadUIDm9iMpkShccUddsA0ImDd6vUqu8bFLExJHePRKXVJHLWafpWoPXKW+Jlf3RXEm5xVg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: DAMON checks the access to each region for every sampling interval, increase the counter of the region, namely nr_accesses if the access was made, and reset the counter for every aggregation interval. The counter is exposed to users to be used as a metric showing the access rate (frequency) of each region. In other words, DAMON provides access rate of each region in every aggregation interval. The aggregation avoids temporal access pattern changes make things confusing. However, this also makes many DAMON-based operations to need to be aligned to the aggregation interval. This can restrict the flexibility and speed of DAMON applications, especially when the aggregation interval is huge. To provide the monitoring results in finer-grained timing with handling of temporal access pattern change, this patchset implements a pseudo-moving sum based access rate metric. It is pseudo-moving sum because strict moving sum implementation would need to keep every last time window values, and that could incur high overhead. Especially in case of the nr_accesses, since the sampling interval and aggregation interval can arbitrarily set and the past values should be maintained for every region, it could be risky. The pseudo-moving sum assumes there were no temporal access pattern change in last discrete time window to remove the needs for keeping the list of the last time window values. As a result, it beocmes not strict moving sum implementation, but provides a reasonable accuracy. Also, it keeps a property of the moving sum. That is, the moving sum becomes same to discrete-window based sum at the time that aligns to the time window. Hence, using the pseudo moving sum based nr_accesses makes no change to users who collect the value for every aggregation interval. SeongJae Park (8): mm/damon/core: define and use a dedicated function for region access rate update mm/damon/vaddr: call damon_update_region_access_rate() always mm/damon/core: implement a pseudo-moving sum function mm/damon/core-test: add a unit test for damon_moving_sum() mm/damon/core: introduce nr_accesses_bp mm/damon/core: use pseudo-moving sum for nr_accesses_bp mm/damon/core: skip updating nr_accesses_bp for each aggregation interval mm/damon/core: mark damon_moving_sum() as a static function include/linux/damon.h | 16 +++++++++- mm/damon/core-test.h | 21 ++++++++++++ mm/damon/core.c | 74 +++++++++++++++++++++++++++++++++++++++++++ mm/damon/paddr.c | 11 +++---- mm/damon/vaddr.c | 22 +++++++------ 5 files changed, 128 insertions(+), 16 deletions(-) base-commit: 85bb49ddd3983b85ab98ad50a69ca1c7380fc63a -- 2.25.1