Received: by 2002:a05:6a10:83d0:0:0:0:0 with SMTP id o16csp159571pxh; Thu, 7 Apr 2022 17:22:09 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyIHuCwcfRU6HG87sLn5900zP1HarxKxKdzMs//uzI1WzVRNOZJg70d5H5qLNQxp1w6K3OS X-Received: by 2002:a05:6a00:124f:b0:4fb:2608:78de with SMTP id u15-20020a056a00124f00b004fb260878demr16459361pfi.27.1649377329299; Thu, 07 Apr 2022 17:22:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1649377329; cv=none; d=google.com; s=arc-20160816; b=U5MUr0pK0A+FXaO0X9Et4vfIkn+iDj315aFbE4sSfLaPM812F6lBbJUy4Xnn0XcdSU epYs0blXL0w1XU8jEK22rmgwVawUboCCjdgrYuk+JQboxItjT9bDR3BCyWiYU7a2uZMO Xx24vvVhq3q7d4HcM3MwH8cZkJxjd4CV+q/rsW96iNe7BEwB3fwf3O1v+YqbKaXm1jAN HgmSoPomQjMGvXhUKCinl6gfJsDGnpRhFrtI4/AVeRAw/uwjRUP1yV+wNYnK+mFOm60T mZroiQ0Y1z7qWOYAE5yBzUbVf2qpJ3za6hBRiDmxGPN6lQEuzwnyuJzqwu0O6/+AXRhC /6gA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:dkim-signature; bh=V2o8XyYQ0xmNcxKBL4HU7d9kJ83bRGbyiA4C3lqn/Jg=; b=qQsoBkM/CXWUPNuvlcDnwaOiKLJmJWUDe1S7S6J0Y9/rY+mF/S1s1Lj9LBYFHpGuzx 4LD+B5M0/1mLoWdxvD+C34EU3PKs6GaXD2NujeuhBXvlosQqspBjPBDunn76AuRsO15u jPvPhfYRRHZnOeqLGw3bfrvJ3OpKI2pRT0D3sCNM87+zj9+nkyLTN7RN7k0+V8zqDHNh aip+7/SvT25xFX4O2uoK+S8XfvXuRu2cEryfMZdu3irN5st5zAIp3+prOG8yaE2ZscMJ DlPVPpSJh2To7u4Hiv1U29f4XLDnc62lz2VgDgtrLSv9hySnAlJiVzCYF3V3bvCmoWRc DyVA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=pHa9t1vY; spf=softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net. [23.128.96.19]) by mx.google.com with ESMTPS id il10-20020a17090b164a00b001bd14e01fc2si3477556pjb.176.2022.04.07.17.21.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Apr 2022 17:22:09 -0700 (PDT) Received-SPF: softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) client-ip=23.128.96.19; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20210112 header.b=pHa9t1vY; spf=softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id 80C85FFB5B; Thu, 7 Apr 2022 16:52:17 -0700 (PDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232647AbiDGXyF (ORCPT + 99 others); Thu, 7 Apr 2022 19:54:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59602 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232656AbiDGXyE (ORCPT ); Thu, 7 Apr 2022 19:54:04 -0400 Received: from mail-vk1-xa33.google.com (mail-vk1-xa33.google.com [IPv6:2607:f8b0:4864:20::a33]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D2C76B1E6 for ; Thu, 7 Apr 2022 16:52:02 -0700 (PDT) Received: by mail-vk1-xa33.google.com with SMTP id w67so1441589vkw.6 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=eoWmiB9fnVKZty4RFc0/bQtZmUVvtlkuhxQEA3UPD9u/4E5ZtGsYVrQv1BaXRI76Mf MX89mG8kfrcHU2rSwV3YN/47yfRcVO1iTrqq0VTdUlkIRrNTYhQm5GPtJ1+r77pUv2RC VX+l9mgt1aR76ZM9z33E/T9NfW+ZjR7E/9zOmvvwWqCntnO3dVeheNNzQcvzE2R/n0ZJ 9mNvnwmiT7u9os4j+OmOzs3PlYDNtJWnksFzq1HQ+V6J7TrnjC38wMs97IaglITgcaQC LJco/oAb8MLz7n4T+Dt2A3+ofCGXAu3c5JWWgxR07RYhnaE1/KJib9ThNsvu+LhBxfZc RNnA== X-Gm-Message-State: AOAM531fUif3TWXiq5xz32AA+VDNt2xxIYtQsG3NjGRpQYd1kxxhmE1x xPEGQutjAuoXhm1/sypZYJo06rpNPU5xt/cKE1JDsQ== 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-Spam-Status: No, score=-9.5 required=5.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE,T_SCC_BODY_TEXT_LINE, USER_IN_DEF_DKIM_WL autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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.