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 9961EC433F5 for ; Tue, 8 Feb 2022 16:50:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BB1C16B0078; Tue, 8 Feb 2022 11:50:12 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B3BAA6B007B; Tue, 8 Feb 2022 11:50:12 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 98D646B007D; Tue, 8 Feb 2022 11:50:12 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay.a.hostedemail.com [64.99.140.24]) by kanga.kvack.org (Postfix) with ESMTP id 8306A6B0078 for ; Tue, 8 Feb 2022 11:50:12 -0500 (EST) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 542CC22FC8 for ; Tue, 8 Feb 2022 16:50:12 +0000 (UTC) X-FDA: 79120200264.05.5CD8E57 Received: from mail-qv1-f43.google.com (mail-qv1-f43.google.com [209.85.219.43]) by imf25.hostedemail.com (Postfix) with ESMTP id BC0C6A0002 for ; Tue, 8 Feb 2022 16:50:11 +0000 (UTC) Received: by mail-qv1-f43.google.com with SMTP id fh9so6655906qvb.1 for ; Tue, 08 Feb 2022 08:50:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cmpxchg-org.20210112.gappssmtp.com; s=20210112; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=uyO1MEQNps5iP9oCUciIE1rzkZYVSZzJb+muZcFYOk4=; b=7XADFpc43QE/qt3E2nOE7ZKJdXQmQHBogj8fnQWh7+4WrlwFlcR/DwHHHOuuOsKMzF ExPTEWDXBgZBHf+ouoy6HcCW2F1IGloyK+6wcpTxC+goATrzrxIK+324QzKWUnCSZyW8 Ri2uC4GQ61xus0satGVJWldH+w/uS8/tp2JUDHoz8Amm6FZJ346hIPhYKIGvMs8CY1vi w3r2Kt7goS4sWztJwu1Qh+B1FjvqM4sFH2hMgeP1PFxsnwhqL8mu/VjtMUo7FoBWqtRm EcgJoePCZR5LmlW/bwoeFY65V8ujtI5jSUJop3tYEbLBYGWyTMcBvlXMlRLxQZ4zEm1T CJLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=uyO1MEQNps5iP9oCUciIE1rzkZYVSZzJb+muZcFYOk4=; b=cNwq83335ttQWJnhIwtp/N00m0sD3/tSZTj+4PDBdPjD3xOSZajnQ26ppKnbDPHfPO fQJuGyBcl3c6AYyGrUJoQNWxdb1fb3ltk3lG9gW6jxkAgB95GSUjSsL1YokFJv61ytER +VciMysVh5a7gWb1WXqnNRDRB58zyFXuW6p9FVPFpip2J9YzAtS5eA6tWS/ARzbMvLMK rpIrSYt9bw1BeWR2L+/Uob8S9SkIqd+yGn1HH/izKLPkzn5g5MXXYVM5zmstp1LppbbY onY29/LSF02c9Ajd3QihctynwIPcawuSMNtOysmI9lDNRyrr02wUDB88p4GP8uxBKYvQ tpFA== X-Gm-Message-State: AOAM531yH1zubSUYoM65g9IBUhQ88WomN38njc5CN1N6rq0UjS3vziuD wxq5uol+vGeBKka8p1sBruRUww== X-Google-Smtp-Source: ABdhPJz+Mim2S0L7J3jzU/RU666khnWwq0OnAnSRMBnKl8t1dS2pUe3shi/y15pML0DetMa4dYFnKQ== X-Received: by 2002:ad4:5ec9:: with SMTP id jm9mr3851203qvb.15.1644339010896; Tue, 08 Feb 2022 08:50:10 -0800 (PST) Received: from localhost (cpe-98-15-154-102.hvc.res.rr.com. [98.15.154.102]) by smtp.gmail.com with ESMTPSA id r7sm7196497qti.69.2022.02.08.08.50.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 08 Feb 2022 08:50:10 -0800 (PST) Date: Tue, 8 Feb 2022 11:50:09 -0500 From: Johannes Weiner To: Yu Zhao Cc: Andrew Morton , Mel Gorman , Michal Hocko , Andi Kleen , Aneesh Kumar , Barry Song <21cnbao@gmail.com>, Catalin Marinas , Dave Hansen , Hillf Danton , Jens Axboe , Jesse Barnes , Jonathan Corbet , Linus Torvalds , Matthew Wilcox , Michael Larabel , Mike Rapoport , Rik van Riel , Vlastimil Babka , Will Deacon , Ying Huang , linux-arm-kernel@lists.infradead.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, page-reclaim@google.com, x86@kernel.org, Brian Geffon , Jan Alexander Steffens , Oleksandr Natalenko , Steven Barrett , Suleiman Souhlal , Daniel Byrne , Donald Carr , Holger =?iso-8859-1?Q?Hoffst=E4tte?= , Konstantin Kharlamov , Shuang Zhai , Sofia Trinh Subject: Re: [PATCH v7 05/12] mm: multigenerational LRU: minimal implementation Message-ID: References: <20220208081902.3550911-1-yuzhao@google.com> <20220208081902.3550911-6-yuzhao@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20220208081902.3550911-6-yuzhao@google.com> X-Rspamd-Queue-Id: BC0C6A0002 X-Stat-Signature: xgarzju79u7ajazk8m8rp6kz98wgc8wa Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=cmpxchg-org.20210112.gappssmtp.com header.s=20210112 header.b=7XADFpc4; dmarc=pass (policy=none) header.from=cmpxchg.org; spf=pass (imf25.hostedemail.com: domain of hannes@cmpxchg.org designates 209.85.219.43 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org X-Rspamd-Server: rspam06 X-Rspam-User: X-HE-Tag: 1644339011-669714 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: Hi Yu, Thanks for restructuring this from the last version. It's easier to learn the new model when you start out with the bare bones, then let optimizations and self-contained features follow later. On Tue, Feb 08, 2022 at 01:18:55AM -0700, Yu Zhao wrote: > To avoid confusions, the terms "promotion" and "demotion" will be > applied to the multigenerational LRU, as a new convention; the terms > "activation" and "deactivation" will be applied to the active/inactive > LRU, as usual. > > The aging produces young generations. Given an lruvec, it increments > max_seq when max_seq-min_seq+1 approaches MIN_NR_GENS. The aging > promotes hot pages to the youngest generation when it finds them > accessed through page tables; the demotion of cold pages happens > consequently when it increments max_seq. Since the aging is only > interested in hot pages, its complexity is O(nr_hot_pages). Promotion > in the aging path doesn't require any LRU list operations, only the > updates of the gen counter and lrugen->nr_pages[]; demotion, unless > as the result of the increment of max_seq, requires LRU list > operations, e.g., lru_deactivate_fn(). I'm having trouble with this changelog. It opens with a footnote and summarizes certain aspects of the implementation whose importance to the reader aren't entirely clear at this time. It would be better to start with a high-level overview of the problem and how this algorithm solves it. How the reclaim algorithm needs to find the page that is most suitable for eviction and to signal when it's time to give up and OOM. Then explain how grouping pages into multiple generations accomplishes that - in particular compared to the current two use-once/use-many lists. Explain the problem of MMU vs syscall references, and how tiering addresses this. Explain the significance of refaults and how the algorithm responds to them. Not in terms of which running averages are updated, but in terms of user-visible behavior ("will start swapping (more)" etc.) Express *intent*, how it's supposed to behave wrt workloads and memory pressure. The code itself will explain the how, its complexity etc. Most reviewers will understand the fundamental challenges of page reclaim. The difficulty is matching individual aspects of the problem space to your individual components and design choices you have made. Let us in on that thinking, please ;) > @@ -892,6 +892,50 @@ config ANON_VMA_NAME > area from being merged with adjacent virtual memory areas due to the > difference in their name. > > +# multigenerational LRU { > +config LRU_GEN > + bool "Multigenerational LRU" > + depends on MMU > + # the following options can use up the spare bits in page flags > + depends on !MAXSMP && (64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP) > + help > + A high performance LRU implementation for memory overcommit. See > + Documentation/admin-guide/mm/multigen_lru.rst and > + Documentation/vm/multigen_lru.rst for details. These files don't exist at this time, please introduce them before or when referencing them. If they document things introduced later in the patchset, please start with a minimal version of the file and update it as you extend the algorithm and add optimizations etc. It's really important to only reference previous patches, not later ones. This allows reviewers to read the patches linearly. Having to search for missing pieces in patches you haven't looked at yet is bad. > +config NR_LRU_GENS > + int "Max number of generations" > + depends on LRU_GEN > + range 4 31 > + default 4 > + help > + Do not increase this value unless you plan to use working set > + estimation and proactive reclaim to optimize job scheduling in data > + centers. > + > + This option uses order_base_2(N+1) bits in page flags. > + > +config TIERS_PER_GEN > + int "Number of tiers per generation" > + depends on LRU_GEN > + range 2 4 > + default 4 > + help > + Do not decrease this value unless you run out of spare bits in page > + flags, i.e., you see the "Not enough bits in page flags" build error. > + > + This option uses N-2 bits in page flags. Linus had pointed out that we shouldn't ask these questions of the user. How do you pick numbers here? I'm familiar with workingset estimation and proactive reclaim usecases but I wouldn't know. Even if we removed the config option and hardcoded the number, this is a question for kernel developers: What does "4" mean? How would behavior differ if it were 3 or 5 instead? Presumably there is some sort of behavior gradient. "As you increase the number of generations/tiers, the user-visible behavior of the kernel will..." This should really be documented. I'd also reiterate Mel's point: Distribution kernels need to support the full spectrum of applications and production environments. Unless using non-defaults it's an extremely niche usecase (like compiling out BUG() calls) compile-time options are not the right choice. If we do need a tunable, it could make more sense to have a compile time upper limit (to determine page flag space) combined with a runtime knob? Thanks!