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 X-Spam-Level: X-Spam-Status: No, score=-13.3 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_IN_DEF_DKIM_WL autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 97DD8C433ED for ; Sat, 24 Apr 2021 04:16:28 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id E91EC613C1 for ; Sat, 24 Apr 2021 04:16:27 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org E91EC613C1 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=google.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 46A9A6B0036; Sat, 24 Apr 2021 00:16:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 41B006B006C; Sat, 24 Apr 2021 00:16:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E2AF6B006E; Sat, 24 Apr 2021 00:16:27 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0008.hostedemail.com [216.40.44.8]) by kanga.kvack.org (Postfix) with ESMTP id 13DDF6B0036 for ; Sat, 24 Apr 2021 00:16:27 -0400 (EDT) Received: from smtpin15.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id B7B9912CB for ; Sat, 24 Apr 2021 04:16:26 +0000 (UTC) X-FDA: 78065948772.15.3DC98B5 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) by imf27.hostedemail.com (Postfix) with ESMTP id B1C2F80192D4 for ; Sat, 24 Apr 2021 04:16:07 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id p6so43593586wrn.9 for ; Fri, 23 Apr 2021 21:16:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=+RJFosm8FHH2Jn0KGRwZnltNO8hwDftaaApIKsuH0kI=; b=vPsrQY60EaNeOA7ZDGwId49uyGwdlyrnVdS69f2LawN1hbdeYe/kXepyDMtZRvUkh3 jR4OTkDycg0YVUbpO1znyY5GBtnfDbLygtgfltvHLSC4/Ni2+XtyMzTvzhHdsDR7yIbw hk6EAXyUNguGK6BJv4jSdujbJxE25ixPJ1VmBJ2GIrfrGesMYZS8BbKkcRNXyfS6QWWT 7tmxNoqhdRW8HVDBQmL6y//O2oPyLUCQwYg4GKcbLLXSQXAVVnbrypTQItZVAI72M8tj mxYIQDOIUPumoELPEfM2KuHmJHd6NBttuqr+UFxTHwG6wYqaNuLw0YnmTrhO6HDO/0oB F24w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=+RJFosm8FHH2Jn0KGRwZnltNO8hwDftaaApIKsuH0kI=; b=YNDJMPuVYuC6zPNwFVV7U60aArK3EIUNwpBDrcXm6BknLuF6QySXPgZfSQnsb1Gy3j MyAXktFiopIXYAY4XM91u2P3+clsaKa4fn4Zy2IJsCwlyyxotoyZHI/S7VEfHbhaefjB TXG0uIX9dle90x5jEfMsLIctR9cHJ3mZdum7ie6yjIaVyM2ruVAbRqJY+oPL3RP8809L DGyTnq4U1EvFpOBkisb1l0LINA5rqr1S/oAGR21elVAdD48wI1Da3Bx8OAc0DEvcR7FR 1UL2fAEb5/boxyjt3X61+TBGwUthiYlDaIlntd0RiCGSaP2pwDpru6cAWH7fdRmFMpjG SlUw== X-Gm-Message-State: AOAM531nxDcYFEhC8PG4tp/ra6fkLJ/lZKQiLTK0nCQZrClIun9LXwpD BzMiQBHySaffQOznkPIIuQQDwx/OrbapT7kEFN4YwQ== X-Google-Smtp-Source: ABdhPJxDPtDbP8/O8pGTZKhqRlwXWFr15MUui2u1oNy5Gd7ROtemc4SLTheDmZuw2EaYsgkgys+dKShgTrSp7TVya1A= X-Received: by 2002:adf:9148:: with SMTP id j66mr8701215wrj.124.1619237785037; Fri, 23 Apr 2021 21:16:25 -0700 (PDT) MIME-Version: 1.0 References: <3ddd4f8a-8e51-662b-df11-a63a0e75b2bc@kernel.dk> <20210413231436.GF63242@dread.disaster.area> <20210414155130.GU3762101@tassilo.jf.intel.com> <20210415030002.GX3762101@tassilo.jf.intel.com> <20210415095708.GA6874@lespinasse.org> <20210424033038.GP1401198@tassilo.jf.intel.com> In-Reply-To: <20210424033038.GP1401198@tassilo.jf.intel.com> From: Yu Zhao Date: Fri, 23 Apr 2021 22:16:12 -0600 Message-ID: Subject: Re: [PATCH v2 00/16] Multigenerational LRU Framework To: Andi Kleen Cc: Michel Lespinasse , Rik van Riel , Ying Huang , Dave Chinner , Jens Axboe , SeongJae Park , Linux-MM , Andrew Morton , Benjamin Manes , Dave Hansen , Hillf Danton , Johannes Weiner , Jonathan Corbet , Joonsoo Kim , Matthew Wilcox , Mel Gorman , Miaohe Lin , Michael Larabel , Michal Hocko , Roman Gushchin , Rong Chen , SeongJae Park , Tim Chen , Vlastimil Babka , Yang Shi , Zi Yan , linux-kernel , lkp@lists.01.org, Kernel Page Reclaim v2 Content-Type: text/plain; charset="UTF-8" X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: B1C2F80192D4 X-Stat-Signature: 6eazsmfcyq5hi4yso7nbr1yxgqmzqyy4 Received-SPF: none (google.com>: No applicable sender policy available) receiver=imf27; identity=mailfrom; envelope-from=""; helo=mail-wr1-f53.google.com; client-ip=209.85.221.53 X-HE-DKIM-Result: pass/pass X-HE-Tag: 1619237767-333646 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 Fri, Apr 23, 2021 at 9:30 PM Andi Kleen wrote: > > > Now the question is how we build the bloom filter. A simple answer is > > to let the rmap do the legwork, i.e., when it encounters dense > > regions, add them to the filter. Of course this means we'll have to > > use the rmap more than we do now, which is not ideal for some > > workloads but necessary to avoid worst case scenarios. > > How would you maintain the bloom filter over time? Assume a process > that always creates new mappings and unmaps old mappings. How > do the stale old mappings get removed and avoid polluting it over time? > > Or are you thinking of one of the fancier bloom filter variants > that support deletion? As I understand they're significantly less > space efficient and more complicated. Hi Andi, That's where the double buffering technique comes in :) Recap: the creation of each new generation starts with scanning page tables to clear the accessed bit of pages referenced since the last scan. We scan page tables according to the current bloom filter, and at the same time, we build a new one and write it to the second buffer. During this step, we eliminate regions that have become invalid, e.g., too sparse or completely unmapped. Note that the scan *will* miss newly mapped regions, i.e., dense regions that the rmap hasn't discovered. Once this step is done, we flip to the second buffer. And from now on, all the new dense regions discovered by the rmap will be recorded into this buffer. Each element in the bloom filter is a hash value from an address of a page table and a node id, indicating this page table has a worth number of pages from this node. A single counting bloom filter works too but it doesn't seem to offer any advantage over double buffering. And we need to handle overflow too.