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 00782ECAAD3 for ; Fri, 2 Sep 2022 01:22:12 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 746E680091; Thu, 1 Sep 2022 21:22:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6CE768008D; Thu, 1 Sep 2022 21:22:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 521D280091; Thu, 1 Sep 2022 21:22:12 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 3D1468008D for ; Thu, 1 Sep 2022 21:22:12 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 1AD11140B1C for ; Fri, 2 Sep 2022 01:22:12 +0000 (UTC) X-FDA: 79865394504.07.8BADC54 Received: from mail-ej1-f49.google.com (mail-ej1-f49.google.com [209.85.218.49]) by imf12.hostedemail.com (Postfix) with ESMTP id D0B394005F for ; Fri, 2 Sep 2022 01:22:11 +0000 (UTC) Received: by mail-ej1-f49.google.com with SMTP id fy31so940992ejc.6 for ; Thu, 01 Sep 2022 18:22:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date; bh=4ekojsMMqY2Pm05Rphb53MHYNyMEIvQwOJ3eVma3ANU=; b=DpE5ySnBVoMrzA8BE5ubvWKgQjB1eCXTMacZXixvZozSowwvy8FN2PZfmG+otQ9CV+ OAf7gWgQnbp0SDJ8le0Tw3/xbHELKX/g6NcRgiey2LlnnGRPV8o72Hletv2uMsURQa3y rYwiT+BKPC/m9v1v6RZ+woAz1ofjW1p559y30t9akOy+/w6kSRD/GjPxNyEJYOavDCXm Ov7Rry9VHU3af8eC6+7+fZ4KGjQKLl2Lfxxs539lVqvhtCJwZ02M3joaNM9ui5UyjxH6 VZnGPJ57zgHXiSdTX+2G4gMUAn1J8TCA2aAybDOArbH04LzR44QuRDzQNQY3k4V5rrOO Lcyg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=4ekojsMMqY2Pm05Rphb53MHYNyMEIvQwOJ3eVma3ANU=; b=QBRgdo0nJFat3tkVJ0h6OH9/QUV0MXp9Ro49IwlUlMPTHGJbHQ1E9KGJYUIbE1urX6 QVZ6Qt4es+NBWqwTDmM2+oH7f5cQ3E4iPvZBkYv+JbrOOIDyldOdGjSDIvS+aV2Hui7S SHNK410hl14T96o+gdjNSJWNB5krrrc9/VJAcsDpTTwdSvw5Yk2mqV/ESEJQUa/jkmAf nKpIGFasdUs4mf6kgKAck1c4sC+EGfaU0P3kr0ljfGlzubKpIaVd5bn3WMqgY1r7FpNX J2LkgD0dV1/xDw1Pjs3MppE8y2R8+uKcF6EBWmmo26P0xo+r07+/7VmZlKJZer4HVvOZ m3kA== X-Gm-Message-State: ACgBeo2NYgglC+CxI638GmZavIgqdVHxXhe57wWmzpWs5Esp8Bdr9JC2 QtIxCqDJro+Cx7IPz642qpmbxhWjnyl7R6WN9hU= X-Google-Smtp-Source: AA6agR7W3a5Sl/Lf3q0qup8swxm27nDGIzxM98seBuNVPpdZiEoOzNDOaGns8RakN4dBbM2m+TBvcVlsmwdczcFz+XY= X-Received: by 2002:a17:906:8462:b0:741:6003:71e4 with SMTP id hx2-20020a170906846200b00741600371e4mr17739965ejc.170.1662081730591; Thu, 01 Sep 2022 18:22:10 -0700 (PDT) MIME-Version: 1.0 References: <20220901221114.81601-1-sj@kernel.org> In-Reply-To: <20220901221114.81601-1-sj@kernel.org> From: Barry Song <21cnbao@gmail.com> Date: Fri, 2 Sep 2022 13:21:59 +1200 Message-ID: Subject: Re: [PATCH 7/8] mm/damon: introduce DAMON-based LRU-lists Sorting To: SeongJae Park Cc: Yu Zhao , Andrew Morton , linux-kernel@vger.kernel.org, damon@lists.linux.dev, linux-mm@kvack.org Content-Type: text/plain; charset="UTF-8" ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1662081731; a=rsa-sha256; cv=none; b=xX7fx1w137C06qZ1qN311kufJmyrctqcig3GkE5rKV05ApsCq9IBYeTwZu/II6WBmp3MDo bOFz05DU3AvkDAFJOw6a8Og9vaRYpjUB30BnnaAOZxwq0IymeViLmVYqoULQvpPJPpZ7zW s0i06+bC7DmjqKexal5x+QXb2T9HhCA= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=DpE5ySnB; spf=pass (imf12.hostedemail.com: domain of 21cnbao@gmail.com designates 209.85.218.49 as permitted sender) smtp.mailfrom=21cnbao@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1662081731; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=4ekojsMMqY2Pm05Rphb53MHYNyMEIvQwOJ3eVma3ANU=; b=jAcFejXJzcMGCx/AOZWAYo/82v9+PkIKHR0xXvjgN2aeCu7i+aDRVKRGxmRAvNEOcUPJbO fWTH16SUMQUD46JVBBbWQQaKCud6JrNJwtpc8yhuTOd0S84xI78TRq3adiEgQMmCN4c61/ txwSCk46+5Y2gdORsUrCPFJdxmpCIsA= Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=DpE5ySnB; spf=pass (imf12.hostedemail.com: domain of 21cnbao@gmail.com designates 209.85.218.49 as permitted sender) smtp.mailfrom=21cnbao@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-Rspam-User: X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: D0B394005F X-Stat-Signature: 5qsg518woa8p8can14gcpwwh4jgp36xx X-HE-Tag: 1662081731-661433 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, Sep 2, 2022 at 10:11 AM SeongJae Park wrote: > > On Fri, 2 Sep 2022 09:40:10 +1200 Barry Song <21cnbao@gmail.com> wrote: > > > On Fri, Sep 2, 2022 at 5:11 AM SeongJae Park wrote: > > > > > > Hi Barry, > > > > > > > > > On Thu, 1 Sep 2022 14:21:21 +1200 Barry Song <21cnbao@gmail.com> wrote: > > > > > > > On Thu, Sep 1, 2022 at 2:03 PM Barry Song <21cnbao@gmail.com> wrote: > > > > > > > > > > On Tue, Jun 14, 2022 at 10:01 AM SeongJae Park wrote: > > > > > > > > > > > > Users can do data access-aware LRU-lists sorting using 'LRU_PRIO' and > > > > > > 'LRU_DEPRIO' DAMOS actions. However, finding best parameters including > > > > > > the hotness/coldness thresholds, CPU quota, and watermarks could be > > > > > > challenging for some users. To make the scheme easy to be used without > > > > > > complex tuning for common situations, this commit implements a static > > > > > > kernel module called 'DAMON_LRU_SORT' using the 'LRU_PRIO' and > > > > > > 'LRU_DEPRIO' DAMOS actions. > > > > > > > > > > > > It proactively sorts LRU-lists using DAMON with conservatively chosen > > > > > > default values of the parameters. That is, the module under its default > > > > > > parameters will make no harm for common situations but provide some > > > > > > level of efficiency improvements for systems having clear hot/cold > > > > > > access pattern under a level of memory pressure while consuming only a > > > > > > limited small portion of CPU time. > > > > > > > > > > > > > Hi SeongJae, > > > > While I believe DAMON pro-active reclamation and LRU-SORT can benefit the system > > > > by either swapping out cold pages earlier and sorting LRU lists before > > > > system has high > > > > memory pressure, I am still not convinced the improvement really comes from the > > > > identification of cold and hot pages by DAMON. > > > > > > > > My guess is that even if we randomly pick some regions in memory and do the same > > > > thing in the kernel, we can also see the improvement. > > > > > > > > As we actually depend on two facts to benefit from DAMON > > > > 1. locality > > > > while virtual address might have some locality, physical address seems > > > > not. for example, > > > > address A might be mapped by facebook, address A + 4096 could be > > > > mapped by youtube. > > > > There is nothing which can stop contiguous physical addresses from > > > > being mapped by > > > > completely irrelevant applications. so regions based on paddr seems pointless. > > > > > > > > 2. accuration > > > > As I have reported it is very hard for damon to accurately track > > > > virtual address since > > > > virtual space is so huge: > > > > https://lore.kernel.org/lkml/CAGsJ_4x_k9009HwpTswEq1ut_co8XYdpZ9k0BVW=0=HRiifxkA@mail.gmail.com/ > > > > I believe it is also true for paddr since paddr has much worse > > > > locality than vaddr. > > > > so we probably need a lot of regions, ideally, one region for each page. > > > > > > > > To me, it seems neither of these two facts are true. So I am more > > > > willing to believe > > > > that the benefits come from areas picked randomly. > > > > > > > > Am I missing something? > > > > > > Thank you for the questions. > > > > > > As you mentioned, DAMON assumes spatial and temporal locality, to trade > > > accuracy for lower overhead[1]. That is, DAMON believes some memory regions > > > would have pages that accessed in similar frequency for similar time duration. > > > Therefore if the access pattern of the system is really chaotic, that is, if > > > every adjacent page have very different access frequency or the access > > > frequency changes very frequently, DAMON's accuracy would be bad. But, would > > > such access pattern really common in the real world? Given the Pareto > > > principle[2], I think that's not always true. After all, many of kernel > > > mechanisms including the pseudo-LRU-based reclamation and the readahead assumes > > > some locality and makes good effect. > > > > + yu zhao > > > > I do believe we have some locality in virtual addresses as they are in > > the same application. > > that is why we can "exploit locality in rmap" here: > > https://lore.kernel.org/linux-mm/20220815071332.627393-8-yuzhao@google.com/ > > > > But for paddr, i doubt it is true as processes use page faults to get > > pages from buddy > > mainly in low order like zero. > > Well, what I can tell for now is that it would depend on the specific system > and workload, but I found some production systems that have such kind of > physical address space locality. yep. I guess for mmu-less systems, spatial locality is more likely to be true. for mmu system, workload using 2MB or 1GB THP will show some locality in physical address as well. but THP_SWP will swap them as a whole, so it seems locality inside a THP doesn't help? as we are not splitting sub pages of THP for reclamation? > > > > > > > > > If your system has too low locality and therefore DAMON doesn't provide good > > > enough accuracy, you could increase the accuracy by setting the upperbound of > > > the monitoring overhead higher. For DAMOS schemes like DAMON_RECLAIM or > > > DAMON_LRU_SORT, you could also increase the minimum age of the target access > > > pattern. If the access pattern is really chaotic, DAMON wouldn't show the > > > regions having the specific access pattern for long time. Actually, definition > > > of the age and use of it means you believe the system's access pattern is not > > > that chaotic but has at least temporal locality. > > > > > > It's true that DAMON doesn't monitor access pattern in page granularity, and > > > therefore it could report some cold pages as hot, and vice versa. However, I'd > > > say the benefit of making right decision for huge number of pages outweighs the > > > risk of making wrong decision for few pages in many cases. > > > > > > After all, it shows some benefit on my test environments and some production > > > systems. I haven't compared that against random pageout or random lru sorting, > > > though. > > > > > > Nevertheless, DAMON has so many rooms for improvement, including the accuracy. > > > I want to improve the accuracy while keeping the overhead low. Also, I know > > > that there are people who willing to do page-granularity monitoring though it > > > could incur high monitoring overhead. As a part of the DAMON accuracy > > > improvement plan, to use that as a comparison target, and to convince such > > > people, I added the page granularity monitoring feature of DAMON to my todo > > > list. I haven't had a time for prioritizing that yet, though, as I haven't > > > heard some clear voice of users for that. I hope the DAMON Beer/Coffee/Tea > > > Chat Series to be a place to hear such voices. > > > > is it possible for us to leverage the idea from "mm: multi-gen LRU: > > support page table walks" > > > > https://lore.kernel.org/linux-mm/20220815071332.627393-9-yuzhao@google.com/ > > > > we pro-actively scan the virtual address space of those processes > > which have been really > > executed then get LRU sorted earlier? > > I didn't read MGLRU patchset thoroughly, but, maybe? > Yes, please read MGLRU, SeongJae. I find some ideas in MGLRU are really good. we might leverage those to improve DAMON as well :-) > > Thanks, > SJ > > > > > > > > > [1] https://docs.kernel.org/mm/damon/design.html#address-space-independent-core-mechanisms > > > [2] https://en.wikipedia.org/wiki/Pareto_principle > > > > > > > > > Thanks, > > > SJ > > Thanks Barry