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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id AF260C433F5 for ; Tue, 8 Feb 2022 16:50:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1383543AbiBHQuO (ORCPT ); Tue, 8 Feb 2022 11:50:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35700 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1383544AbiBHQuN (ORCPT ); Tue, 8 Feb 2022 11:50:13 -0500 Received: from mail-qv1-xf2a.google.com (mail-qv1-xf2a.google.com [IPv6:2607:f8b0:4864:20::f2a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E05A2C061576 for ; Tue, 8 Feb 2022 08:50:11 -0800 (PST) Received: by mail-qv1-xf2a.google.com with SMTP id c14so6605365qvl.12 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=VeJfSdruXGqrlBaBNCaNMUQFqsH0JP6x6BsfNZq1xWGS7azhqjw0lt1+1DVXhA9o3E gb5wGub22kDLC28KfJNoaPg02Qw7OKKZZDvpalrQGLNe9Nj47BkPk1YzIo2nbBII1Myj Orh71XwefigFYZjCjBBTO6bze5H/X7KDqEqodVZtPJ2VG2mLrcvw6/QUcO5YpP8tjO+X f63o6ljTMttDPaNdyFmKx0ZVZpTNhO5yFvcCIHt5e5JQx6lCUJUHASUyHrr8F3rQIKvO hXcOk5I+UNpqUzzg/9djZ72ONW7qn+lvMx86sp59ZTLAUvcmLjIf5k/9WgFaAb18KpwO 1CAA== X-Gm-Message-State: AOAM531T7Rjh5dN7juVljdUrohgUi/yI7aAodkJPrtbqpQ+D6xZlCRBO MPJqeCX/u/pClItgQM+ZHEJUbA== 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> Precedence: bulk List-ID: X-Mailing-List: linux-doc@vger.kernel.org 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!