Received: by 2002:a05:6a10:a841:0:0:0:0 with SMTP id d1csp1839638pxy; Fri, 23 Apr 2021 19:36:06 -0700 (PDT) X-Google-Smtp-Source: ABdhPJynvhPfxkBVVz6ccsUJq+TmIcA+XsW/trM3IMFuWF3R6Y1jDzaDipiPKEP3Hb46fzwZ/sZz X-Received: by 2002:a17:907:9607:: with SMTP id gb7mr6946125ejc.380.1619231766598; Fri, 23 Apr 2021 19:36:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1619231766; cv=none; d=google.com; s=arc-20160816; b=GqPbMdwWe1Ix/9CCHj2w6Rc9TeOcx8VJaAVVEhibYFZuajPQp6wHFD+PluAWRkNfEU wCTJMbUeKtSGq+MKnzyEasUgHsRJgMuyRQU9gsPmMlZZvfA42t9u4c2RupkqtUfUhdzr QP7UfDbUTDWjT5vbSeB855CMDYkf8I7IuElEXBD3QsJv/sNtFN0DjOXq0i5sXRKGsYcI qvfnCZAQfSLoXFmSzfaWdaeORAzthgVgCx6xyk2Z4Lq0NV5azUqjplz3nbAtnc+1dn/f 5nVv6DbYhl0PeaB6TXnZIPsYgXdZwYLDxfcMpQN1UAdl0g1iijQRz4kfiGOwaF6XyNnm 002A== 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=HOmGJz1YMkX1d3zPs6qU93d5OQzAANLQ/MDgx0IN2Dw=; b=cRKBvuVKS1yPuspxq5xezAdFfIQ7nTNX6yWsMtCTkMM4krGUs7wVOwqTEhWs2tasbe f/UT1gVDir/of1xWKQ3A7cucKf77e8ea0EaErijiDvJP53JCZj+CJbICNqjx2r5ZdPPN kc/YwSp59Z0SZ6p/8dPxenwQWOYensQpMTbKldiZiZfiLttSDZexWHd4xS5qXFePZrWQ i81FH7DKaqWcxcNozbnjkhSAxujSVObsrWtOISCTUyU5KyEDPnk+b+U2kEWMbUJhlQQf Xv7b4b7vuZTNVW1VZBZnqrv0cgGh5viVwAt1OlpHH6+q8yPORtbgVDFPNn/AN8FwqrEp xTBA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=ta9rsseP; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 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 vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id du3si6961602ejc.302.2021.04.23.19.35.31; Fri, 23 Apr 2021 19:36:06 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=ta9rsseP; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233185AbhDXCeR (ORCPT + 99 others); Fri, 23 Apr 2021 22:34:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59638 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232619AbhDXCeQ (ORCPT ); Fri, 23 Apr 2021 22:34:16 -0400 Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5FF8BC061574 for ; Fri, 23 Apr 2021 19:33:37 -0700 (PDT) Received: by mail-wr1-x42c.google.com with SMTP id r7so38125402wrm.1 for ; Fri, 23 Apr 2021 19:33:37 -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=HOmGJz1YMkX1d3zPs6qU93d5OQzAANLQ/MDgx0IN2Dw=; b=ta9rssePip7edcrE34ZasASEDthvSGLseGE9GD7p1VWVPVsb4A/J/LzedHXnEfFnO4 4PhlFUL/muvuQLE/n0X85ELGxCdSxjS2AQwAd4NGFcstib+mYp43s1Plaien3T06MJUT 7C0UHN9ecI8ljBFRgJnkIDow8EQ2RSlTR1s3M1YiJzBu8kDxnxAmAJkVZH84D7wJTOyi M6gZoMaGLsI99D7Z9uw9BfIYFew5qjMl5Es/hSuUxWjlIzPB5nBQ2wqIncv/JI0sUR95 BalsjO0T/qLJzmm4DsFpTcdMLAgsgcRRmUPcD7G/OMkMx4apxasvglqhDvuQ2OifWSai D5DQ== 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=HOmGJz1YMkX1d3zPs6qU93d5OQzAANLQ/MDgx0IN2Dw=; b=BaIKbRZ8UqMTHN6spT0el7EZTtmA9efw14jFAkzRIMxDgvnNomfhdcx/KCgn5v+/Yv x10seyBccBNwF2BJHY2YzZ3wiyxHyHttIgzPi+uGdIhKhayy4ExUJi2p92ZOX6lK4HzD uv1N6tF1KhlxLKY8RLVTvOUKnmxrR1jDW+D7SAm8oEu0V/g9ft1ECwlHpn3qMjL0+w4z J5iNuokOHBK6LuakBRdQ9yMB0ecMZaY64r3II89G3YW9qM9QWoKFCWRIGF2SrkTtFQbn Bhp8BwMINkyx58yiQLZIK/+x5ruPf720tDN66qu0WKbJeWVTOtLhH1TENN/DiQ/qa/jU 9PeQ== X-Gm-Message-State: AOAM532t9qfqNq/MvIfv5tDfkqavNlNbiDNTnSjvyYC8UQa2gtd9nAP2 BLz+i+RBtGdHcm89R/s+Mp/N/ZYXE0AlevQVLPZyBQ== X-Received: by 2002:adf:e381:: with SMTP id e1mr7961383wrm.323.1619231609325; Fri, 23 Apr 2021 19:33:29 -0700 (PDT) MIME-Version: 1.0 References: <20210413075155.32652-1-sjpark@amazon.de> <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> In-Reply-To: <20210415095708.GA6874@lespinasse.org> From: Yu Zhao Date: Fri, 23 Apr 2021 20:33:17 -0600 Message-ID: Subject: Re: [PATCH v2 00/16] Multigenerational LRU Framework To: Michel Lespinasse Cc: 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 , Andi Kleen Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sun, Apr 18, 2021 at 12:48 AM Michel Lespinasse wrote: > On Thu, Apr 15, 2021 at 01:13:13AM -0600, Yu Zhao wrote: > > Page table scanning doesn't replace the existing rmap walk. It is > > complementary and only happens when it is likely that most of the > > pages on a system under pressure have been referenced, i.e., out of > > *inactive* pages, by definition of the existing implementation. Under > > such a condition, scanning *active* pages one by one with the rmap is > > likely to cost more than scanning them all at once via page tables. > > When we evict *inactive* pages, we still use the rmap and share a > > common path with the existing code. > > > > Page table scanning falls back to the rmap walk if the page tables of > > a process are apparently sparse, i.e., rss < size of the page tables. > > Could you expand a bit more as to how page table scanning and rmap > scanning coexist ? Say, there is some memory pressure and you want to > identify good candidate pages to recaim. You could scan processes with > the page table scanning method, or you could scan the lru list through > the rmap method. How do you mix the two - when you use the lru/rmap > method, won't you encounter both pages that are mapped in "dense" > processes where scanning page tables would have been better, and pages > that are mapped in "sparse" processes where you are happy to be using > rmap, and even pges that are mapped into both types of processes at > once ? Or, can you change the lru/rmap scan so that it will efficiently > skip over all dense processes when you use it ? Hi Michel, Sorry for the late reply. I was out of town and am still catching up on emails. That's a great question. Currently the page table scanning isn't smart enough to know where dense regions are. My plan was to improve it gradually but it seems it couldn't wait because people have major concerns over this. At the moment, the page table scanning decides if a process is worthy by checking its RSS against the size of its page tables. This can only avoid extremely sparse regions, meaning the page table scanning will scan regions that ideally should be covered by the rmap, for some worse case scenarios. My next step is to add a bloom filter so it can quickly determine dense regions and target them only. Given what I just said, the rmap is unlikely to encounter dense regions, and that's why the perf profile shows its cpu usage drops from ~30% to ~5%. 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. Does it make sense?