From patchwork Thu Oct 31 16:12:03 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: SeongJae Park X-Patchwork-Id: 13858165 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 96A4FD767E1 for ; Thu, 31 Oct 2024 16:12:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0FE736B0088; Thu, 31 Oct 2024 12:12:13 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0AE8B6B008A; Thu, 31 Oct 2024 12:12:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EDF296B008C; Thu, 31 Oct 2024 12:12:12 -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 D1FFF6B0088 for ; Thu, 31 Oct 2024 12:12:12 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 8E503A1697 for ; Thu, 31 Oct 2024 16:12:12 +0000 (UTC) X-FDA: 82734387834.09.1C0F32B Received: from nyc.source.kernel.org (nyc.source.kernel.org [147.75.193.91]) by imf19.hostedemail.com (Postfix) with ESMTP id 0AA3B1A0017 for ; Thu, 31 Oct 2024 16:11:36 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=lwKi8rgs; spf=pass (imf19.hostedemail.com: domain of sj@kernel.org designates 147.75.193.91 as permitted sender) smtp.mailfrom=sj@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1730391086; 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=b43vGpm2I03ilS4F+c2T4EhOH8q9TUobYjnKEZ4Ma5s=; b=DK9gNsDEDzzwE1U6JdW0Msv5XWNvLCQ0/zzkrduR/g0qRWpuStR9OXEepSHAs+o4QmUvY4 w8q02sG8gs1aOJfzEGxKSgRMEJYyjIkuvvWpE0+AugpQAgx84DiW/BAnIcS1viEFxeTJgK /YwKSU6q2ynNgRy//yfKWQDm8hZ1sUw= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730391086; a=rsa-sha256; cv=none; b=NsxQz2UK6bCj1NBC57Xt2hLRuV61OxkGHCwXLnOVkpa68YOw6ZZkgCVRqIa9U+CwmDcOJk +lSbYBA6sEx4u9lRGo51S8pjWLB/h2tIbH3QPEfoznIVgOgARmjcPaOqztXzz+gtz9D7nT 1NaJuvAOnt97HaBQZtwJCtu5AFA2IUE= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=lwKi8rgs; spf=pass (imf19.hostedemail.com: domain of sj@kernel.org designates 147.75.193.91 as permitted sender) smtp.mailfrom=sj@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by nyc.source.kernel.org (Postfix) with ESMTP id AB21EA443B1; Thu, 31 Oct 2024 16:10:14 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id D1A0CC4FDF8; Thu, 31 Oct 2024 16:12:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1730391130; bh=eJEmZyDPLbC02Dw1bjFmNYjwx8wPuh7E/dUJfe6XCXs=; h=From:To:Cc:Subject:Date:From; b=lwKi8rgs00fdO2QE9BMW6hi2NXzjy6NXFt7VzFB2pNgQAHatvcKXpR3WB3yncLNUx aGLF8/lLm9TUuegjSXYis0qqiaYe6g4ONQBdL+prOUET9SemlRs3jn3dGHimQxAL+b 6FzPwJEqBm3xdSi5brDCH4GbYcYBDHOodpPWFQH43SeBm08a5luahqa4pJ040IyYDU d4CG/Ul6tP4nNy6oXvhX8odQygIvHNmCb2J0ABRRASiqaLa9BU88GE0eSasSRlsdAW VOojFRiT2qVwNjAsmlI/FQniRvMppkdS+M004rbPZ3RYFDIriFNcaTThiO1ivglrlk 7W7AeU4utKkxg== From: SeongJae Park To: Andrew Morton Cc: SeongJae Park , damon@lists.linux.dev, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Guenter Roeck , stable@vger.kernel.org Subject: [PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input() Date: Thu, 31 Oct 2024 09:12:03 -0700 Message-Id: <20241031161203.47751-1-sj@kernel.org> X-Mailer: git-send-email 2.39.5 MIME-Version: 1.0 X-Stat-Signature: oud4k85kzq5me5c3rt8qo6c1pqtcc33w X-Rspam-User: X-Rspamd-Queue-Id: 0AA3B1A0017 X-Rspamd-Server: rspam02 X-HE-Tag: 1730391096-714542 X-HE-Meta: U2FsdGVkX19Q4Ooa/N2lsGZx3s4B81AxgWOWr9sQWU3K+wxHF+eQOCDrPeAZyqlyfs5Hfe0MtsPSwNAIEuAJS3JMapZdwx3Hikko5bRdAd6EW78IV2xppKso/pKa7EW+0w8MfgKku7v+YzYV8p6fiDNUx0CtdOHRu5U85RxNEvXz7Hg4qlPiRIoWL74tqlO8qwjxclvXiVKTTtHh4w/MI82SFwvkYOGX6rSPzXmmz9LeZElX/CY3TlfVhjzgi2/Qkj/JNC7Ck9Z9FAu4d+hTg/P2ObCPKuIe7HfKqdtalVBBmi+tBqp0428R29CPyNcJXMdZ/y2iuqn5EyCxNcq98AFt4Mgh3w4lTnVhTHQsrl76ZstQ+j/NOTKo8Pnsh9a0FYEmAUxM6A8RrQ16Esgu9Lh6GyiQ4fqNhpGEV4E9rngQdqblweA3P10G0E/rswHWHOJlq97dahYnvRZv5aUgjMVt5odZjJJyxwHzRMwst/Ck4tsd5wjK7S8DriNEImBocYVQP7vF8YRQu1cBipxPNdpcKFnT0FI7h9Of1BPEMHMOE/REv+7FN0w/7T/CCsyqszCzTKwSKDoTEV0wTd71FcIP2+JKfPQaXasiBPGKCcosQ3SqzDynIE9+OM2D0YVfam7hYY+zGyiogyR0NfH5FsQ84IKL6rSGLN+uMJaSxnn8jFFa2yJ06qE2LdUay+R8CTi49FaTelg5M8iqQxrw7fXQIAhftwJgecMvL4YmHMirMDPUV1QCFQCg40BO+mIzu0CCJdWPgYCG0y5p+0itHoNFBBqdOtg7S6XYQJ+Cq9R1+PDA/n7RxlwGK2wRpJ0FFKzqRgiXHPD7NMNCBwDXA2M4+DbWJSnyjNKLK/SiSXGocSYG0KT7Cu5IpfgucU5zevfr1tjiEUe+UWX5E7zdbWusLFmwB0x9Xj7bwMsqDvAJf7d8Dq1Y3AJfKxZJtnuT8y9f7itj5DmlTKuTf4M EYdGjlVc FIlLjvggHU0OGrCRvNhAILw+q2hGvdsXP8dH75zAPTXJmUCBvEXGF8iXIH4kSS5wO7/R6lkPg8rf2jj+CzQE5sVZORx2dGen7yBWrzZ4vftLeX+ZnpFqmeS/5+vTOp45zZH5BCGRjZtV723V/DYFFBL4jHM3TkvctvqG/pk/hQ++bqxL5yFHRUuSRQnZK310put5Um+K5sFHTQ07eCgYISPN+VMKPr29Wp9HOEp5vJ4zXxrnFM4fkqeURXyjcyUcuOtB+Fc0aXZfS+i92kQYDIr0lggDQkJGXjwf9+Xc+VijWA5jE6MV5Qg+aFPICsXPzbwvlt1+MMMW7LMo= 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: List-Subscribe: List-Unsubscribe: damon_feed_loop_next_input() is inefficient and fragile to overflows. Specifically, 'score_goal_diff_bp' calculation can overflow when 'score' is high. The calculation is actually unnecessary at all because 'goal' is a constant of value 10,000. Calculation of 'compensation' is again fragile to overflow. Final calculation of return value for under-achiving case is again fragile to overflow when the current score is under-achieving the target. Add two corner cases handling at the beginning of the function to make the body easier to read, and rewrite the body of the function to avoid overflows and the unnecessary bp value calcuation. Reported-by: Guenter Roeck Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning") Cc: # 6.8.x Signed-off-by: SeongJae Park Tested-by: Guenter Roeck --- Changes from RFC (https://lore.kernel.org/20240905172405.46995-1-sj@kernel.org) - Rebase on latest mm-unstable and cleanup code mm/damon/core.c | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-) diff --git a/mm/damon/core.c b/mm/damon/core.c index a83f3b736d51..27745dcf855f 100644 --- a/mm/damon/core.c +++ b/mm/damon/core.c @@ -1456,17 +1456,31 @@ static unsigned long damon_feed_loop_next_input(unsigned long last_input, unsigned long score) { const unsigned long goal = 10000; - unsigned long score_goal_diff = max(goal, score) - min(goal, score); - unsigned long score_goal_diff_bp = score_goal_diff * 10000 / goal; - unsigned long compensation = last_input * score_goal_diff_bp / 10000; /* Set minimum input as 10000 to avoid compensation be zero */ const unsigned long min_input = 10000; + unsigned long score_goal_diff, compensation; + bool over_achieving = score > goal; - if (goal > score) + if (score == goal) + return last_input; + if (score >= goal * 2) + return min_input; + + if (over_achieving) + score_goal_diff = score - goal; + else + score_goal_diff = goal - score; + + if (last_input < ULONG_MAX / score_goal_diff) + compensation = last_input * score_goal_diff / goal; + else + compensation = last_input / goal * score_goal_diff; + + if (over_achieving) + return max(last_input - compensation, min_input); + if (last_input < ULONG_MAX - compensation) return last_input + compensation; - if (last_input > compensation + min_input) - return last_input - compensation; - return min_input; + return ULONG_MAX; } #ifdef CONFIG_PSI