From patchwork Tue Sep 12 18:45:08 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kairui Song X-Patchwork-Id: 13382046 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 E61D4EE3F0B for ; Tue, 12 Sep 2023 18:45:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 479276B0148; Tue, 12 Sep 2023 14:45:41 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4290C6B0149; Tue, 12 Sep 2023 14:45:41 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 27C276B014A; Tue, 12 Sep 2023 14:45:41 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 110AF6B0148 for ; Tue, 12 Sep 2023 14:45:41 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D61AA80CB5 for ; Tue, 12 Sep 2023 18:45:40 +0000 (UTC) X-FDA: 81228824040.30.3ADCE7B Received: from mail-oi1-f181.google.com (mail-oi1-f181.google.com [209.85.167.181]) by imf16.hostedemail.com (Postfix) with ESMTP id 004F1180020 for ; Tue, 12 Sep 2023 18:45:38 +0000 (UTC) Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=TsEJA3+x; spf=pass (imf16.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.167.181 as permitted sender) smtp.mailfrom=ryncsn@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1694544339; h=from:from:sender:reply-to: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=gjfuji7UEHE75khrS+0yR4vY9yLEHy5K3t7jmjwKaUo=; b=VZXEvzXQtUC5ff8/rXWa9kXwuw27pfJGBzPN+z4eOYfBCyqQtm0AYW9GQ8lnY4vrSdeiue 31iErdogIor2cAsnD5eQCsdMcTkJWinT2hL1bpfiNjwg6M5gC1kT4DZ2ZlLq2+radiiObX CZtprmFfmMMQV/4axiuq7nSXKnm3Oqo= ARC-Authentication-Results: i=1; imf16.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=TsEJA3+x; spf=pass (imf16.hostedemail.com: domain of ryncsn@gmail.com designates 209.85.167.181 as permitted sender) smtp.mailfrom=ryncsn@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694544339; a=rsa-sha256; cv=none; b=nxAoay4YQ386M80vdN0smyvnhuJgRB2rGER15FesItLWdEb20KOdyhxZNszgY0qSAGQyc8 2a0gKRrFiprPmbbm3Sko05q0dnJSXS6xxcIwAKAkxh9+onxOwEo3sy7/m1Hx1qYpW05y32 epWpbBbC+rfeeBFDa1HM0SHiW8v2QNQ= Received: by mail-oi1-f181.google.com with SMTP id 5614622812f47-3a812843f0fso3682598b6e.2 for ; Tue, 12 Sep 2023 11:45:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1694544337; x=1695149137; darn=kvack.org; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:from:to:cc:subject :date:message-id:reply-to; bh=gjfuji7UEHE75khrS+0yR4vY9yLEHy5K3t7jmjwKaUo=; b=TsEJA3+xYSRTSoQvV9KYEE8ZuRZfOeLAzudzjWrtJA/Y+fmxLBSOPZfSsXV/uqGLMM C8a1uocYD9n7oRQDM2C+jwwZzpXZ8SehjPqvSOkMNGwG5ceGdaLF+X7MR5d9Lrk8ADH/ XD3zRBp1Jhx4GTW8fPruVZCf2Og20+mV04W3bYevohCIOp6VRoAbvU5dir4bkyqHJBFy CWHRXx4qyp41oalh/n65RBnXg8QGvGgR9SO8ignKsqqZHui2K7YL6cprRLM9hJ0ENPQ8 p7xxMhn85mPGtrx1ed8za98KYQvEQi4+4Oe2Aytz1colScjitWx5RBaTLdn+PgO4rbmS nGQg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694544337; x=1695149137; h=content-transfer-encoding:mime-version:reply-to:references :in-reply-to:message-id:date:subject:cc:to:from:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=gjfuji7UEHE75khrS+0yR4vY9yLEHy5K3t7jmjwKaUo=; b=i/Hic1Obx2OXoQPLs2eUjb5D7X7P/Q8VnL9hMzu3rTXd42jqNDqZRU8PHDNJL4Qjfd W5J06vozn53V+b7h6765CnQS0fP70ry5zO6E7RveZ0qJ/BFbkfhKm54VW60qaN2vDFyT R1ajNmmbj1sp6fTFTo96qx2rIltGUf7IK21wSW16WpFpKtDBJ9goC8rdNILb7W+/egJo GQdfCm5ubHHRCY2V0/SjcWTjjbdIiFmuQPc1fJ8YYDFiV7/paJz89i6W8fw75sJ5N83F bZ6SyAy5UST2tEYHpugZYB7TSUYjuwq+J/mIfBxgVEr48Qb+vfUpiqoNO3QsQ78vWDPE 27Hw== X-Gm-Message-State: AOJu0Yy4TeS3WRs70GMF0mjo8jI0m8eYn5rdPNSlog6aWlJwACuuVpRa 1U90YdU3ixVBcpNW7oc9+fmJ3NGU14bFK1yIBxKBsQ== X-Google-Smtp-Source: AGHT+IHyWdNnqK0qjnu7TwqtfVWChgp49JttbBNQpuhoyVR+YbsMFEjpzShFP3xExPsLxO1wSb3peg== X-Received: by 2002:a05:6808:13d5:b0:3a8:3d5b:aad6 with SMTP id d21-20020a05680813d500b003a83d5baad6mr667457oiw.55.1694544337174; Tue, 12 Sep 2023 11:45:37 -0700 (PDT) Received: from KASONG-MB2.tencent.com ([124.127.145.18]) by smtp.gmail.com with ESMTPSA id q18-20020a63bc12000000b00553b9e0510esm7390605pge.60.2023.09.12.11.45.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 12 Sep 2023 11:45:36 -0700 (PDT) From: Kairui Song To: linux-mm@kvack.org Cc: Andrew Morton , Yu Zhao , Roman Gushchin , Johannes Weiner , Michal Hocko , Hugh Dickins , Nhat Pham , Yuanchu Xie , Suren Baghdasaryan , "T . J . Mercier" , linux-kernel@vger.kernel.orng, Kairui Song Subject: [RFC PATCH v2 2/5] workingset: update comment in workingset.c Date: Wed, 13 Sep 2023 02:45:08 +0800 Message-ID: <20230912184511.49333-3-ryncsn@gmail.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20230912184511.49333-1-ryncsn@gmail.com> References: <20230912184511.49333-1-ryncsn@gmail.com> Reply-To: Kairui Song MIME-Version: 1.0 X-Rspamd-Queue-Id: 004F1180020 X-Rspam-User: X-Stat-Signature: ycu7x6xu1kayznpjukxndgx1rirc8xzo X-Rspamd-Server: rspam01 X-HE-Tag: 1694544338-94537 X-HE-Meta: U2FsdGVkX1+8taV4VK4OLM3DTbaACHyG6YOtdHE7qEc5AzzYJePi37lJ8MOaEFOSiE1NF/Pp6Y8Ah5MidEZJTxsfR30UoqTt4uP355dv2KpUxZRCjZWBtdjd7EFOwcoGJbzDv8tyJq6oIWNa7PP9EZLTQkndC8b1Dte+jNCbs1y1zQdnCq/Y3wYFVTvFzc7QziD2acqDlFftFzLjdmUNdlg21q7LnB/LZOuSIsS+BJSKJK0CDEg87PN2q2xo6bwGY8UnUSJMfI7zi08JZCFGNeN73OEMON0bV2GFPnyCR4tGDaT9+cvWGmG5J/KhbL3gknaDhQgs4aAQb+wHKkb5wntv/AXA/15S0tULCVkHzTdOX2DTqUiuuRrDNwelgD4LCFyH/9ZwBZxIsk4fUqXd/S6qtPSZ3PVS/xpORC/rboS8iP7F3daEFl9V0V4sqnY0GEkL2ztYfumae0x82Ff8uC52++3F1uekoyqOL9aBzEA8zCcUL1lpYSIeEW6MVyWGze3IvkUZOBfzfagLjC3XhkxeZj5e9h9HTyxt+i3tMXFlA/C5Hq0eov0DPnElVq89uogYcUEnCuVocVFUvgWv53fNkSc1DDFTZmCdV4N4X7D17v5/5Ja2+PdvP51MJaiM0EYGAPQeYa9WSok7vAZyus5NT5h1tLtAQvO3H+vWCqYhXl8Q/4avFBMvLT0PHGXSdIrFyTSZ/jrMZPomVzTaH1m6WbVkY79gl9GllHE8RJV7E32cBGAIMNG7SK9j02kkSfUjUOOKTi6wgef5AY/n+TL+ht4wGdSAUx9GntJajuFNAF6vlO3GTsDrJ9eoFMJMuEAedqO04kzaNgxzDomcni4QxDvH/MvlF6k7dCEZHs339JhFXlh7zb3L7DrMuw3nyulXW/lN6FWIlXZGX7nZJrj4XzzzeZsmWdqVkuEmFh2VjHRGqbvsLGO6dnBVGIPf3BVW5ch6FceVOTAmpd2 3w/5D11D 4iljxG5glzaWQI0oEq2aVi7uCz4404vENci8yYQeXuHEYpojN0m7VQI6kytQUpaFgwme7DhmNLjhcHjz1O73ZFQ7saj7H9KRCgRT/i8Z0Ep3Dcxf1y0yhOflZbl5DKLuIrqOONqPn8ho9Pm/YuG+e5S6EJ1S+C6D23jQqjzj94p/+jMtoGO7+Qrz2Mybwj+jXS/BQdrb79bGffKczPnW4g4x10fUQwdOT/MqskR9p7GuXMFgU2VcSfHYdOZWH8eMmUx6jGM8WZn+t/4kktEf7UCWNrlcSBawyQa543Xw95KWJcUuw4NRrDIYnOYMyyJ3uSKySQ6SSbqZdUJ3aqvy313ffBffCKMzKGW3JK10+3uk9GH1W3xr75aUTXDRXlrpG52cwL3CPLs6rqDXiS30/XmFPwj5uy+D/aUsmd7rrHZT3iDEJaYFxiD0d5v8mtaZp954q7nWCnJUqHF3Py6kKR7Wb+A1j7kA/YNTnL/8y7T4qbNt1Juwnaw4Lu37C0IMsSq8gsEoFuY2Zsus0q0nRUfELYK2iK+YJz+dhz+pgSiswYpF/3XRUn2jCCHJeiGvbVLdwYgXEFl6lLrE0ktcJKQJvdgzKSBPHJaTd3tSUiPmZfcv0LITFz0rg0zfp7a49Uw8X 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: Kairui Song Update the comments according to new implementation. Signed-off-by: Kairui Song --- mm/workingset.c | 98 ++++++++++++++++++++++--------------------------- 1 file changed, 44 insertions(+), 54 deletions(-) diff --git a/mm/workingset.c b/mm/workingset.c index babda11601ea..b5c565a5a959 100644 --- a/mm/workingset.c +++ b/mm/workingset.c @@ -64,74 +64,64 @@ * thrashing on the inactive list, after which refaulting pages can be * activated optimistically to compete with the existing active pages. * - * Approximating inactive page access frequency - Observations: + * For such approximation, we introduce a counter `nonresistence_age` (NA) + * here. This counter increases each time a page is evicted, and each evicted + * page will have a shadow that stores the counter reading at the eviction + * time as a timestamp. So when an evicted page was faulted again, we have: * - * 1. When a page is accessed for the first time, it is added to the - * head of the inactive list, slides every existing inactive page - * towards the tail by one slot, and pushes the current tail page - * out of memory. + * Let SP = ((NA's reading @ current) - (NA's reading @ eviction)) * - * 2. When a page is accessed for the second time, it is promoted to - * the active list, shrinking the inactive list by one slot. This - * also slides all inactive pages that were faulted into the cache - * more recently than the activated page towards the tail of the - * inactive list. + * +-memory available to cache-+ + * | | + * +-------------------------+===============+===========+ + * | * shadows O O O | INACTIVE | ACTIVE | + * +-+-----------------------+===============+===========+ + * | | + * +-----------------------+ + * | SP + * fault page O -> Hole left by previously faulted in pages + * * -> The page corresponding to SP * - * Thus: + * Here SP can stands for how far the current workflow could push a page + * out of available memory. Since all evicted page was once head of + * INACTIVE list, the page could have such an access distance of: * - * 1. The sum of evictions and activations between any two points in - * time indicate the minimum number of inactive pages accessed in - * between. + * SP + NR_INACTIVE * - * 2. Moving one inactive page N page slots towards the tail of the - * list requires at least N inactive page accesses. + * So if: * - * Combining these: + * SP + NR_INACTIVE < NR_INACTIVE + NR_ACTIVE * - * 1. When a page is finally evicted from memory, the number of - * inactive pages accessed while the page was in cache is at least - * the number of page slots on the inactive list. + * Which can be simplified to: * - * 2. In addition, measuring the sum of evictions and activations (E) - * at the time of a page's eviction, and comparing it to another - * reading (R) at the time the page faults back into memory tells - * the minimum number of accesses while the page was not cached. - * This is called the refault distance. + * SP < NR_ACTIVE * - * Because the first access of the page was the fault and the second - * access the refault, we combine the in-cache distance with the - * out-of-cache distance to get the complete minimum access distance - * of this page: + * Then the page is worth getting re-activated to start from ACTIVE part, + * since the access distance is shorter than total memory to make it stay. * - * NR_inactive + (R - E) + * And since this is only an estimation, based on several hypotheses, and + * it could break the ability of LRU to distinguish a workingset out of + * caches, so throttle this by two factors: * - * And knowing the minimum access distance of a page, we can easily - * tell if the page would be able to stay in cache assuming all page - * slots in the cache were available: + * 1. Notice that re-faulted in pages may leave "holes" on the shadow + * part of LRU, that part is left unhandled on purpose to decrease + * re-activate rate for pages that have a large SP value (the larger + * SP value a page have, the more likely it will be affected by such + * holes). + * 2. When the ACTIVE part of LRU is long enough, chanllaging ACTIVE pages + * by re-activating a one-time faulted previously INACTIVE page may not + * be a good idea, so throttle the re-activation when ACTIVE > INACTIVE + * by comparing with INACTIVE instead. * - * NR_inactive + (R - E) <= NR_inactive + NR_active + * Combined all above, we have: + * Upon refault, if any of the following conditions is met, mark the page + * as active: * - * If we have swap we should consider about NR_inactive_anon and - * NR_active_anon, so for page cache and anonymous respectively: - * - * NR_inactive_file + (R - E) <= NR_inactive_file + NR_active_file - * + NR_inactive_anon + NR_active_anon - * - * NR_inactive_anon + (R - E) <= NR_inactive_anon + NR_active_anon - * + NR_inactive_file + NR_active_file - * - * Which can be further simplified to: - * - * (R - E) <= NR_active_file + NR_inactive_anon + NR_active_anon - * - * (R - E) <= NR_active_anon + NR_inactive_file + NR_active_file - * - * Put into words, the refault distance (out-of-cache) can be seen as - * a deficit in inactive list space (in-cache). If the inactive list - * had (R - E) more page slots, the page would not have been evicted - * in between accesses, but activated instead. And on a full system, - * the only thing eating into inactive list space is active pages. + * - If ACTIVE LRU is low (NR_ACTIVE < NR_INACTIVE), check if: + * SP < NR_ACTIVE * + * - If ACTIVE LRU is high (NR_ACTIVE >= NR_INACTIVE), check if: + * SP < NR_INACTIVE * * Refaulting inactive pages *