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 64196C433EF for ; Tue, 26 Apr 2022 07:43:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9BE4F6B0075; Tue, 26 Apr 2022 03:43:07 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 96D796B0078; Tue, 26 Apr 2022 03:43:07 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7E5FE6B007B; Tue, 26 Apr 2022 03:43:07 -0400 (EDT) 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 6C1A26B0075 for ; Tue, 26 Apr 2022 03:43:07 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay11.hostedemail.com (Postfix) with ESMTP id 33B5B809BA for ; Tue, 26 Apr 2022 07:43:07 +0000 (UTC) X-FDA: 79398239214.05.CCD7AFC Received: from mail-vs1-f52.google.com (mail-vs1-f52.google.com [209.85.217.52]) by imf05.hostedemail.com (Postfix) with ESMTP id 7D5B910004D for ; Tue, 26 Apr 2022 07:43:00 +0000 (UTC) Received: by mail-vs1-f52.google.com with SMTP id f32so16673266vsv.1 for ; Tue, 26 Apr 2022 00:43:06 -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=F6hORQhWD4R4PBBaL15o7cQDBZSUWYx9+THQUkS8oik=; b=nXY/jyTlv7QAuUsIJPC7aUL8xu31SPzL1bxZweM6Hbt56IqaVYOxOqVmdLCuEH7OCi FUYT8m9jDymm04MoMEF3hNYKUGc4hcmG6bS3lNCUKekqAgf7bXYLMCCFJdVK7ZTTQoUN LeQaEzTmHc7Ehq7uWn9SY4+ygDmk8YOugiY/F4wliaccWAY4pyuc/MRBTdsPK0chG/2y dyfCk6HxBfCr+SfSf1dxCTreUXtNre0vItXXdjMAv4E0MDdSxPldz0rSkhE2IZPEPtgj PMgud5bgboNo28FLcNcjPBLHuNgaiJ1CVnanYSVbXTOOgvoC5YjdZQdmMK/LUhpjov3c Y6nQ== 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=F6hORQhWD4R4PBBaL15o7cQDBZSUWYx9+THQUkS8oik=; b=sMBrrJKfJvodkXpmXPBaRYSF593+Rp09gu4fGWZabLv6MjpgdvKISrpO+OPwg9sw/V 2iFpDcvNI4aWlmDeYwi4d5BvyeMpeaE9/PjmXSjoG3G80VzeFBmzQkKSayR8bTL4pNgR AB2FaP8CKVD4/rQRIyCcxn/VR0a0YgnMu2SdnDOnp8arToKzMBj/9cwT367PaFl39470 kqJsPdu2Dl98wLQAdDFXHUgdJnkvs78wdPvOmxJnrwdLKj6TJULT5LML6f/hj0dBZT6c g9+VOtxrTVI2oc17PyZH/elLeMczrpaD64V0kSASw6HoCY7G85mQ2AoNJqUugAWfRRCq NxzQ== X-Gm-Message-State: AOAM533xsGiZ1CVSYvrNP8t/UhgV/F/J1ZCfNrOsDo2AQGXWfi+j0BQl RtFN1QoPY9JqHDZNzFCFY3qU3IoWHrqtohLOW+BsfA== X-Google-Smtp-Source: ABdhPJwrYwHJliqqvdxOxEXGiUwfDiSxoM+Qnd1xHIJRZWoed1Am6bjcaOL5Pk10UbnYyCsT4xwysfqq8d6vEqmiqek= X-Received: by 2002:a67:cb02:0:b0:32c:2690:be39 with SMTP id b2-20020a67cb02000000b0032c2690be39mr6421711vsl.81.1650958985634; Tue, 26 Apr 2022 00:43:05 -0700 (PDT) MIME-Version: 1.0 References: <20220407031525.2368067-1-yuzhao@google.com> <20220407031525.2368067-15-yuzhao@google.com> <20220411191645.91078752f29b82aea7ee508c@linux-foundation.org> In-Reply-To: <20220411191645.91078752f29b82aea7ee508c@linux-foundation.org> From: Yu Zhao Date: Tue, 26 Apr 2022 01:42:29 -0600 Message-ID: Subject: Re: [PATCH v10 14/14] mm: multi-gen LRU: design doc To: Andrew Morton Cc: Stephen Rothwell , Linux-MM , Andi Kleen , Aneesh Kumar , Barry Song <21cnbao@gmail.com>, Catalin Marinas , Dave Hansen , Hillf Danton , Jens Axboe , Jesse Barnes , Johannes Weiner , Jonathan Corbet , Linus Torvalds , Matthew Wilcox , Mel Gorman , Michael Larabel , Michal Hocko , Mike Rapoport , Rik van Riel , Vlastimil Babka , Will Deacon , Ying Huang , Linux ARM , "open list:DOCUMENTATION" , linux-kernel , Kernel Page Reclaim v2 , "the arch/x86 maintainers" , 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-Stat-Signature: 8xcakr39fpz1nhh694y4ri35cqyo6dnw Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b="nXY/jyTl"; spf=pass (imf05.hostedemail.com: domain of yuzhao@google.com designates 209.85.217.52 as permitted sender) smtp.mailfrom=yuzhao@google.com; dmarc=pass (policy=reject) header.from=google.com X-Rspam-User: X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 7D5B910004D X-HE-Tag: 1650958980-928124 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 Mon, Apr 11, 2022 at 8:16 PM Andrew Morton wrote: > > On Wed, 6 Apr 2022 21:15:26 -0600 Yu Zhao wrote: > > > Add a design doc. > > > > > > ... > > > > +Design overview > > +=============== > > +Objectives > > +---------- > > +The design objectives are: > > + > > +* Good representation of access recency > > +* Try to profit from spatial locality > > +* Fast paths to make obvious choices > > +* Simple self-correcting heuristics > > + > > +The representation of access recency is at the core of all LRU > > +implementations. In the multi-gen LRU, each generation represents a > > +group of pages with similar access recency. Generations establish a > > +common frame of reference and therefore help make better choices, > > +e.g., between different memcgs on a computer or different computers in > > +a data center (for job scheduling). > > Does MGLRU have any special treatment for used-once pages? Yes. Single-use pages are assumed to be the cheapest to reclaim: "The first tier contains single-use unmapped clean pages, which are the best bet." > > +Exploiting spatial locality improves efficiency when gathering the > > +accessed bit. A rmap walk targets a single page and does not try to > > +profit from discovering a young PTE. A page table walk can sweep all > > +the young PTEs in an address space, but the address space can be too > > +large to make a profit. The key is to optimize both methods and use > > +them in combination. > > + > > +Fast paths reduce code complexity and runtime overhead. Unmapped pages > > +do not require TLB flushes; clean pages do not require writeback. > > +These facts are only helpful when other conditions, e.g., access > > +recency, are similar. With generations as a common frame of reference, > > +additional factors stand out. But obvious choices might not be good > > +choices; thus self-correction is required. > > + > > +The benefits of simple self-correcting heuristics are self-evident. > > +Again, with generations as a common frame of reference, this becomes > > +attainable. Specifically, pages in the same generation can be > > +categorized based on additional factors, and a feedback loop can > > +statistically compare the refault percentages across those categories > > +and infer which of them are better choices. > > + > > +Assumptions > > +----------- > > +The protection of hot pages and the selection of cold pages are based > > +on page access channels and patterns. There are two access channels: > > + > > +* Accesses through page tables > > +* Accesses through file descriptors > > + > > +The protection of the former channel is by design stronger because: > > + > > +1. The uncertainty in determining the access patterns of the former > > + channel is higher due to the approximation of the accessed bit. > > +2. The cost of evicting the former channel is higher due to the TLB > > + flushes required and the likelihood of encountering the dirty bit. > > +3. The penalty of underprotecting the former channel is higher because > > + applications usually do not prepare themselves for major page > > + faults like they do for blocked I/O. E.g., GUI applications > > + commonly use dedicated I/O threads to avoid blocking the rendering > > + threads. > > + > > +There are also two access patterns: > > + > > +* Accesses exhibiting temporal locality > > +* Accesses not exhibiting temporal locality > > + > > +For the reasons listed above, the former channel is assumed to follow > > +the former pattern unless ``VM_SEQ_READ`` or ``VM_RAND_READ`` is > > +present, and the latter channel is assumed to follow the latter > > +pattern unless outlying refaults have been observed. > > What about MADV_SEQUENTIAL? Or did we propogate that into the fd? MADV_SEQUENTIAL is VM_SEQ_READ. I think you mean POSIX_FADV_SEQUENTIAL. We don't need to propagate it to the fd. Pages sequentially accessed through fd, i.e., detected by mark_page_accessed(), fall into the single-use category. > > +Workflow overview > > +================= > > +Evictable pages are divided into multiple generations for each > > +``lruvec``. The youngest generation number is stored in > > +``lrugen->max_seq`` for both anon and file types as they are aged on > > +an equal footing. The oldest generation numbers are stored in > > +``lrugen->min_seq[]`` separately for anon and file types as clean file > > +pages can be evicted regardless of swap constraints. These three > > +variables are monotonically increasing. > > + > > > > ... > > > > +Summary > > +------- > > +The multi-gen LRU can be disassembled into the following parts: > > + > > +* Generations > > +* Page table walks > > +* Rmap walks > > +* Bloom filters > > +* The PID controller > > + > > +The aging and the eviction is a producer-consumer model; specifically, > > +the latter drives the former by the sliding window over generations. > > +Within the aging, rmap walks drive page table walks by inserting hot > > +densely populated page tables to the Bloom filters. Within the > > +eviction, the PID controller uses refaults as the feedback to select > > +types to evict and tiers to protect. > > It's cool to see a PID controller in there. > > How do we know that it converges well, that it doesn't exhibit instability, etc? Divergence can be easily avoided by using sane parameters. A more specific problem for our use case is how to establish a (relative) time domain. We can't just use wall clock since different CPUs run at the different speeds. Even for the same CPU, it scans pages at different rates under different memory pressure. So generations serve as a time dimension. For each new generation, we refresh the PID controller to minimize the chance of it locking in a bad state. It may make poor choices now and then, but it should never make poor choices all the time.