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 2D1E1C433EF for ; Thu, 7 Apr 2022 23:52:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 661A16B0072; Thu, 7 Apr 2022 19:52:13 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 637716B0074; Thu, 7 Apr 2022 19:52:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4D85A6B0075; Thu, 7 Apr 2022 19:52:13 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0177.hostedemail.com [216.40.44.177]) by kanga.kvack.org (Postfix) with ESMTP id 3F6B86B0072 for ; Thu, 7 Apr 2022 19:52:13 -0400 (EDT) Received: from smtpin24.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id F05CCA5A6A for ; Thu, 7 Apr 2022 23:52:02 +0000 (UTC) X-FDA: 79331733684.24.36318FE Received: from mail-vk1-f177.google.com (mail-vk1-f177.google.com [209.85.221.177]) by imf31.hostedemail.com (Postfix) with ESMTP id 9222B20004 for ; Thu, 7 Apr 2022 23:52:02 +0000 (UTC) Received: by mail-vk1-f177.google.com with SMTP id b81so3484095vkf.1 for ; Thu, 07 Apr 2022 16:52:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=V2o8XyYQ0xmNcxKBL4HU7d9kJ83bRGbyiA4C3lqn/Jg=; b=pHa9t1vY4G3g2veZzfNaljZ/ODjXhV2qKJlnku7tStXx/0bNUioBEP3vV3f0BDiuK6 hH94GBax6Xp/sQJXPDobV4hjMyHFpCJOJaggMaEnDIAAW4ogVzp/3xpwWmhnl/FmXBHo f9FIDTu1gAk8+OOMPOS4KCSGJkzTxlwjzsTeW2yWq86SPpiyjw0UvzuGv2S6NxLXZIKJ +/Oe9syDdzEZuz/BrOKZT0KJEH6QF4YyK93gFRcaGmj715NClbnKJHCwJOqcw4s5H8SC VNHBGY74iMRpwF+Afqjt3G9ynR6r7jacBDvoE93qsSq7iW+qGFGJVpn6Sshd0TVf8skQ QRIw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=V2o8XyYQ0xmNcxKBL4HU7d9kJ83bRGbyiA4C3lqn/Jg=; b=XttaNYmxoNHMHIWAwbtneD0A8c02yzWVOn1BvvUUBnXjHSunjEDwh11m0AshoERVqg RiLVmDYbNd81VsAmFvDuM6VkGyCFXk0J8yarS8Bpy7l9eEZMw9YyFgum2RMQkExVXNix P8jAk4eXJWxOgKNsI99Bby3uqTXg9f6yhCC0Kc8/7+wimnx4o4GJJhe9EupegIQkOrl6 TD12LWRtufGYn03hn6mHDif53+5c0D5ecgmq02BRUObZh5GmL96k63M0lTn5SAv+FZoJ lW5nnbUz3IOxWyzeObGLuIcJ0+LqTLwSBmT89wBOmLV/7tjIpEM+wLr+2bLy7BBSJ1iC xT7A== X-Gm-Message-State: AOAM5302RfMFJoaY9rxZCjQTdz2H/5q4puK3ao122dV4LqEwLP8OOT2V RPevo8BszolpEpPMLCk8TEqgGcC0mSZ8B7DKLFIZAQ== X-Google-Smtp-Source: ABdhPJw/ZEsQZOlZeReph1+ASuuLZlJIuOVM82pvmZCPJ8cvFd3dbcfY3do0xiB4PlkDl4vZ7xT9XS2v6fqp8nCNOS4= X-Received: by 2002:a1f:a9cb:0:b0:33e:d145:85f0 with SMTP id s194-20020a1fa9cb000000b0033ed14585f0mr6025223vke.7.1649375521681; Thu, 07 Apr 2022 16:52:01 -0700 (PDT) MIME-Version: 1.0 References: <20220309021230.721028-1-yuzhao@google.com> <20220309021230.721028-8-yuzhao@google.com> In-Reply-To: From: Yu Zhao Date: Thu, 7 Apr 2022 17:51:50 -0600 Message-ID: Subject: Re: [PATCH v9 07/14] mm: multi-gen LRU: exploit locality in rmap To: Barry Song <21cnbao@gmail.com> Cc: Andrew Morton , Linus Torvalds , Andi Kleen , Aneesh Kumar , Catalin Marinas , Dave Hansen , Hillf Danton , Jens Axboe , Jesse Barnes , Johannes Weiner , Jonathan Corbet , Matthew Wilcox , Mel Gorman , Michael Larabel , Michal Hocko , Mike Rapoport , Rik van Riel , Vlastimil Babka , Will Deacon , Ying Huang , LAK , Linux Doc Mailing List , LKML , Linux-MM , Kernel Page Reclaim v2 , x86 , Brian Geffon , Jan Alexander Steffens , Oleksandr Natalenko , Steven Barrett , Suleiman Souhlal , Daniel Byrne , Donald Carr , =?UTF-8?Q?Holger_Hoffst=C3=A4tte?= , Konstantin Kharlamov , Shuang Zhai , Sofia Trinh , Vaibhav Jain Content-Type: text/plain; charset="UTF-8" X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 9222B20004 X-Stat-Signature: 1ieebdesnjy9xcm98z7ntgtrkb9ipof3 Authentication-Results: imf31.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=pHa9t1vY; dmarc=pass (policy=reject) header.from=google.com; spf=pass (imf31.hostedemail.com: domain of yuzhao@google.com designates 209.85.221.177 as permitted sender) smtp.mailfrom=yuzhao@google.com X-Rspam-User: X-HE-Tag: 1649375522-827390 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: On Wed, Apr 6, 2022 at 9:46 PM Barry Song <21cnbao@gmail.com> wrote: > > On Thu, Apr 7, 2022 at 3:04 PM Yu Zhao wrote: > > > > On Wed, Apr 6, 2022 at 8:29 PM Barry Song <21cnbao@gmail.com> wrote: > > > > > > On Wed, Mar 9, 2022 at 3:48 PM Yu Zhao wrote: > > > > > > > > Searching the rmap for PTEs mapping each page on an LRU list (to test > > > > and clear the accessed bit) can be expensive because pages from > > > > different VMAs (PA space) are not cache friendly to the rmap (VA > > > > space). For workloads mostly using mapped pages, the rmap has a high > > > > CPU cost in the reclaim path. > > > > > > > > This patch exploits spatial locality to reduce the trips into the > > > > rmap. When shrink_page_list() walks the rmap and finds a young PTE, a > > > > new function lru_gen_look_around() scans at most BITS_PER_LONG-1 > > > > adjacent PTEs. On finding another young PTE, it clears the accessed > > > > bit and updates the gen counter of the page mapped by this PTE to > > > > (max_seq%MAX_NR_GENS)+1. > > > > > > Hi Yu, > > > It seems an interesting feature to save the cost of rmap. but will it lead to > > > possible judging of cold pages as hot pages? > > > In case a page is mapped by 20 processes, and it has been accessed > > > by 5 of them, when we look around one of the 5 processes, the page > > > will be young and this pte is cleared. but we still have 4 ptes which are not > > > cleared. then we don't access the page for a long time, but the 4 uncleared > > > PTEs will still make the page "hot" since they are not cleared, we will find > > > the page is hot either due to look-arounding the 4 processes or rmapping > > > the page later? > > > > Why are the remaining 4 accessed PTEs skipped? The rmap should check > > all the 20 PTEs. > > for example page A is the neighbour of page B in process 1, when we do rmap > for B, we look-around and clear A's pte in process 1. but A's ptes are > still set in > process 2,3,4,5. It makes no difference because it's too insignificant. The goal is not to give several million pages unique timestamps and sort them; it's to partition pages on the orders one tenth to a few seconds and quickly find some reasonable candidates. Temporal locality gets weaker exponentially over time. Even on small systems, the difference is not measurable if several thousand pages used in the last few seconds are chosen over another several thousand pages used in the last minute.