From patchwork Fri Sep 15 02:52:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 13386313 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 02112EDE989 for ; Fri, 15 Sep 2023 02:53:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 439F06B02EF; Thu, 14 Sep 2023 22:53:07 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3EAA76B02F2; Thu, 14 Sep 2023 22:53:07 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2D81F6B02F3; Thu, 14 Sep 2023 22:53:07 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 1DF5C6B02EF for ; Thu, 14 Sep 2023 22:53:07 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id DB5A2801DE for ; Fri, 15 Sep 2023 02:53:06 +0000 (UTC) X-FDA: 81237309972.21.CD2C972 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf03.hostedemail.com (Postfix) with ESMTP id B5E8620008 for ; Fri, 15 Sep 2023 02:53:04 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=cI0cRs6q; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf03.hostedemail.com: domain of sj@kernel.org designates 145.40.73.55 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=1694746385; 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=543nhK1IPl9Jpo1hsmWEbS+0QfkL2YjCC2FfQLT+dqI=; b=2PL69AVojfkO2S5ACnqyAhlP181fZtY8V/D/CBe9429hL4C6AUvJp3f5tkyCVf+SpeDRLP W500xq8gPBPLjBJSppYMqTx7erIC3sbFR0n/ojC4A6Y4akx9WRFnh426evpV9Q6QuhAoax aqKX+qA5RUEvqqDYX7jjpW3NQyonY84= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=cI0cRs6q; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf03.hostedemail.com: domain of sj@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=sj@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694746385; a=rsa-sha256; cv=none; b=tVZFCNXY/mhVuNXC5TmF0S/d1sW5KQMH1Xy6RvSgYllrRRXtLqdPUkDskWv8nNjSoz6X5w 6ZPQUsCNJJzHl0xRBrZrcHwsMTo52+oP36j/8sKHOTAA1+psNObD0V86uvOyw4uAWaM3VW m5L9p1AYVHWUrTKkkMqzwnHLj6GEM3s= 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 sin.source.kernel.org (Postfix) with ESMTPS id 570DECE2974; Fri, 15 Sep 2023 02:53:01 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 095D2C433C8; Fri, 15 Sep 2023 02:52:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1694746379; bh=BMoIA/XytQAickyMtxvDt0cV0B7GH433aHBEMFeeRZA=; h=From:To:Cc:Subject:Date:From; b=cI0cRs6qX5hHpd59KhlA3hhK/Qql5/OjdtMEa3olBNhsnYd/e3op+jcl3KLu0BV8w RiEYfVAoYEvsFOzZvj27inW/LGydZnbhhHXGcPjfnz25pHn0jwDd1ILy8UKvbN9zB3 OK2C7gXEQnKz3Vr60XXbCjyF8tPWZE+++a5tVe21EWqxU++Ci5bCOlRqQBxQ4vju+w gJq25kZYHVM3a46zVBvfPUAT8vRgQy5n9GUlelf6ALlF6imhHL/rAQnc/UTJ3iv4tG +16xC6MX6g3x/v2SqaDqjBK3e9BuOsJedv6ba6keD2wIfOpwEeZAjRZzjMnjab2s+h 5uTX7Yzl3Svog== From: SeongJae Park To: Andrew Morton Cc: SeongJae Park , 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: [PATCH 0/8] mm/damon: provide pseudo-moving sum based access rate Date: Fri, 15 Sep 2023 02:52:43 +0000 Message-Id: <20230915025251.72816-1-sj@kernel.org> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 X-Rspamd-Queue-Id: B5E8620008 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 4nu17nw99rd6d7ke6udn9ssps6or8ygk X-HE-Tag: 1694746384-794273 X-HE-Meta: U2FsdGVkX1+k8Uz1SOMu5Ssi765i7G/sxG2/nazgWhMaGpqd0iLX8zOa4FSZMS/y8TqLi3IqYc08xYwi13MN/9wZd4Dgj2ADVXhuaLoi5E34yBoBN2Zes6nRCf7vC4seWZX/JvGZgPUMBxR2YYDdjDD9xevixWQ1xamJuOejkQapnaGJ53Vkglg+L1tiAgfzwjGRE1h+UFRIFFIQcMg22TERiwt7+FEAv9bh8bSP80eUlRadgOFEgqU/6+H9BAuLV38BENcp8mKqgaxm1ORgXEEOIt1sDnPc1X7xt91fCesOIXIYEyD9xUxNui/3qMZpfErt30J1G0iFPQfohbLF9rknvwLrYAfwNohDp7YpV5wdLlGwGkyKZKbGGDu5erC0laDzeC1u0q1E9mVrHvzgJmJyHFFqOrz4LTF4DlnJF5N4wSKSYenETcJcfY8MSHR/4LXLTIQQrBQUrS7GmaGvCVZGuh0lMl6Q+v4DGTR7zXkUX80ba1gAjaAILDuEOBye5hBe8I3nsgrDDlz14ZNfLwfQu2UEPUGydlwOH5RkmgQ0bW12s+6SgV3aS/Rin9/l5Oc/S2NWRbq0VBAIRi+aAHgnxnKBcysOss+ezEkzkM7XpeRCtpS6FIIErt3si9M8Gf5spgemTA4uzbox7vCKY/v61zsB0o8MfuI4/Rmt2NDNutv5gJiwzVz6ekD/A28D1ayZ+RoLB2NWmkmRkMzZnvP1BjpofEqfnNHEpgYgb8wILg4qXNo2+M2HGLTczRAl7ujOAtO3+1GwBMPY30+a1v/MQogGrAemG8GXu7j84VxEBqAoCJ0RE9yZuLQ3AsEmPQU+dC2MVxHQMZhVtKIMUxy8wnhucX/wlCGnGL0BLBlCLvh6h1J7LefKO48wf0BkxHQg0nCb21rblN6+iQKNGF93y5KvPa/BjD/1p5g0oPoShYhA4nCvClum6B5MhvpMh4Yk5vVQcCJJTaBlIEk a37hziX6 6NCkafmi0P2Q1ynbQrjo+URvFemQXZMgzCfBUcbEWyUK5dEODIlt6IKDfB7dplKAqr4iEytc5o9Jx7kx0w/0tsVJBQ+dbJMl6FaAtzc5AOR5HnrhuWTt5tWH1SyKUwQQd7P9VVyrzM/Y1tH/HucYRJ6BIy6jcOoQfVn4shE1U2JK52Qx/bUkYJ3vHF7wYdJd2PSrmMt28XNZ6WDQ7DqWJX2xrLRJXkuZAIrQK9kB8W40HFOP01rhiDu1nYmt01gARFI2v+V3wyaMjWIXGUTSqmwYeTIQDjs5IGIQqj9YCb7PSbXVqyq8eNTMcn86OD5MZH0qdp96H/gL6qB6tLnExaG6nXg== 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: Changes from RFC (https://lore.kernel.org/damon/20230909033711.55794-1-sj@kernel.org/) - Rebase on latest mm-unstable - Minor wordsmithing of coverletter DAMON checks the access to each region for every sampling interval, increase the access rate counter of the region, namely nr_accesses, if the access was made. For every aggregation interval, the counter is reset. The counter is exposed to users to be used as a metric showing the relative 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 making things confusing. However, this also makes a few DAMON-related operations to unnecessarily need to be aligned to the aggregation interval. This can restrict the flexibility of DAMON applications, especially when the aggregation interval is huge. To provide the monitoring results in finer-grained timing while keeping 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 all values for last time window, and that could incur high overhead of there could be arbitrary number of values in a time window. 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 an important 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. This means using the pseudo moving sum based nr_accesses makes no change to users who shows the value for every aggregation interval. Patches Sequence ---------------- The sequence of the patches is as follows. The first four patches are for preparation of the change. The first two (patches 1 and 2) implements a helper function for nr_accesses update and eliminate corner case that skips use of the function, respectively. Following two (patches 3 and 4) respectively implement the pseudo-moving sum function and its simple unit test case. Two patches for making DAMON to use the pseudo-moving sum follow. The fifthe one (patch 5) introduces a new field for representing the pseudo-moving sum-based access rate of each region, and the sixth one makes the new representation to actually updated with the pseudo-moving sum function. Last two patches (patches 7 and 8) makes followup fixes for skipping unnecessary updates and marking the moving sum function as static, respectively. 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: a5b7405a0eaa74d23547ede9c3820f01ee0a2c13