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 2F029C6FD1C for ; Thu, 23 Mar 2023 15:19:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 99F976B0072; Thu, 23 Mar 2023 11:19:04 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 94FB36B0074; Thu, 23 Mar 2023 11:19:04 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7EFDB6B0075; Thu, 23 Mar 2023 11:19:04 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 6FD976B0072 for ; Thu, 23 Mar 2023 11:19:04 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 37898806DD for ; Thu, 23 Mar 2023 15:19:04 +0000 (UTC) X-FDA: 80600521008.27.844EAE8 Received: from mail-ed1-f45.google.com (mail-ed1-f45.google.com [209.85.208.45]) by imf29.hostedemail.com (Postfix) with ESMTP id F2ABE120024 for ; Thu, 23 Mar 2023 15:19:01 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=Ud8sCemO; spf=pass (imf29.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.45 as permitted sender) smtp.mailfrom=yosryahmed@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1679584742; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=xzcfL5cGbbB3FNQKTJn4qTYU62le43s53MGWHPWiK2M=; b=a1frk2G1eDp1CoFYp+HJwh9rzHP/wKvJ4f22N2Djr8Ot86J5hA8wR+iZkC0Ajy2H9/RCV2 Vne0KwzeaQLW9UszF7PG8Qx5hsth41U/bJGJq3UEiVY8c1Yw4BK19E6PtOU08Z6owtVjlW eTlhcRyoASFjJ4v3qhLweNG/eDEEeZk= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=Ud8sCemO; spf=pass (imf29.hostedemail.com: domain of yosryahmed@google.com designates 209.85.208.45 as permitted sender) smtp.mailfrom=yosryahmed@google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1679584742; a=rsa-sha256; cv=none; b=uNEirVvknrhFmlhwsdCv9uD8J9oLXzEWMQtv2phdQDnQ/m92rm7iFQv2rJB2okqc6GXHZB /mRrGa7PvJc9JSFO3OANKRXBMs3uL+jfOW7LhVbY2DtEQHBzW7DiVh7Xyf6IC+SErWz2Rs VmstiTaAVeMvd/yTuWnwmV/ieN3zWCU= Received: by mail-ed1-f45.google.com with SMTP id eh3so88128009edb.11 for ; Thu, 23 Mar 2023 08:19:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; t=1679584740; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=xzcfL5cGbbB3FNQKTJn4qTYU62le43s53MGWHPWiK2M=; b=Ud8sCemOj3G6ca/edHJ8VgZFHScNi2ZhQIjary/dYhw8boIOOEPpcwpWmIqZ1Beob0 S7mMIlU/3MtbHnXuI1oSYGR6TBjuKmJUfc2uqiXReW/iK6BJIXKIqTN+8nSmsc/JRoOI UQrXzZSKV8LB5DM+qXefjGztHlOOQWTGt+yngdi3xvaQCPUIYPrwXpWM7QS7d/8pyTYh a5Iov7SYKVrHfsi1tFM3fkcg8XnwccoK46QAvXlN23BEckVs+8+W8zLseu72VTPKx3D7 p+1RZuJ47LEoEiCK1k9UKYDfamwPJa3EktKI7xW7TSTIxVowqaYlvMWjd0uqFC8K9vqL dCIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679584740; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xzcfL5cGbbB3FNQKTJn4qTYU62le43s53MGWHPWiK2M=; b=z/1RuqRbfNd1eotWYlSInkyxfIKUMdxig0kfJqBdvhxtiGZZjexxrZyztxEwYacuqi M7JfP4P4spMiSqNQHXxenWcDyRP+CykqZ77/JJtFwTx8GTS2KZ7IefKWUr+ALn8YdBZF FPvEvkhbXLuq/BBBy1vDuXxK9FH/+R5mY6FYUa32+zS+q1/NbK8aGnuUQmYvdAI4jt/7 vT+bjqmap0q9LT/N5RX1AVwJL9NfPtEN/3HIQ2MM6ZuvApTFLAzevESYMaJMFMxAHhk6 iu/frXJhFxlBdZwL95vbRvF/y7Wv6fRI29YLGZAu2VUVOnTS6IceknQW/QC/+He1VFuh /C9Q== X-Gm-Message-State: AO0yUKV26j0+sq/95Nw6aZ1xslmsHphoYukZ4LgbEzsLmYXr0AnhH51K Sm0h83q5yGxTEDisuaFLEL1B+PEgxo/2cc+nvNd91g== X-Google-Smtp-Source: AK7set/bbSuqXEcBVREGpwTA9D4UeWyXGcnFeMcWGDu5QcQcmWMUaFamvqXDdpHpB7lX4QANtdQXLIMIsDNfNLKLbgQ= X-Received: by 2002:a17:906:6d6:b0:933:f6e8:26d9 with SMTP id v22-20020a17090606d600b00933f6e826d9mr5305337ejb.15.1679584740146; Thu, 23 Mar 2023 08:19:00 -0700 (PDT) MIME-Version: 1.0 References: <87356e850j.fsf@yhuang6-desk2.ccr.corp.intel.com> <87y1o571aa.fsf@yhuang6-desk2.ccr.corp.intel.com> <87o7ox762m.fsf@yhuang6-desk2.ccr.corp.intel.com> <87bkkt5e4o.fsf@yhuang6-desk2.ccr.corp.intel.com> <87y1ns3zeg.fsf@yhuang6-desk2.ccr.corp.intel.com> <874jqcteyq.fsf@yhuang6-desk2.ccr.corp.intel.com> <87v8isrwck.fsf@yhuang6-desk2.ccr.corp.intel.com> <87bkkkrps8.fsf@yhuang6-desk2.ccr.corp.intel.com> In-Reply-To: <87bkkkrps8.fsf@yhuang6-desk2.ccr.corp.intel.com> From: Yosry Ahmed Date: Thu, 23 Mar 2023 08:18:23 -0700 Message-ID: Subject: Re: [LSF/MM/BPF TOPIC] Swap Abstraction / Native Zswap To: "Huang, Ying" Cc: Chris Li , lsf-pc@lists.linux-foundation.org, Johannes Weiner , Linux-MM , Michal Hocko , Shakeel Butt , David Rientjes , Hugh Dickins , Seth Jennings , Dan Streetman , Vitaly Wool , Yang Shi , Peter Xu , Minchan Kim , Andrew Morton , Aneesh Kumar K V , Michal Hocko , Wei Xu Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Stat-Signature: u3oyibujfseg1rygwhgx36aih84ahpwb X-Rspam-User: X-Rspamd-Queue-Id: F2ABE120024 X-Rspamd-Server: rspam06 X-HE-Tag: 1679584741-4203 X-HE-Meta: U2FsdGVkX1/4mHUXSLoz0rNQZDnq5xMjxhQ661e5CN8a04GH1jVZB5hwiTacqaDDsFDX5HzQ64hgRrAaXpq9qzZwpXtCM+SmQcu0cK5ow0A7516EbLxzjeRCmji6lU9RVv093KKUDRoAvQ/RKZJtTqCcTbTo9CAuYm/wuDW7z95Ws9/x1f+T4gVhKphaG4eWODwBZBaHCRfssri+M7lGBLKYA8qJAJHs/egMDkgoWOUFbVG3c50fh2VG+qF6v/AQTZWAmaUbaUS3uS+HpzwbVmKU2pYMOL3XFNR0U43sj6qPVfjeyoNya1xTlcmS68b+J77/EHCEoLYgZHgeeysY9mQU+npD9eOguOHl/5WzVMFNBIC5JZipmY9XzJpEAXTsoFe9j0ZrgTMzGsqMYr7vg5Td3Gwb1minUDECEXf/IJYtZI91lVL6wcQjRzCp4hXHitpC+sjduh1h1pZC+uHhHCKOW79MjbUfNYRfU84ff49bTCVUXPjwBY5HAFDeQlfyv9KsFkF124BhVFy9Id+yd7XjZbPeDcArrxXiQxHSYMu1ADbKUnJRdO1tTY2cj3k4STZbhRFDjhAj+sJm39FLipe6R+GdUfjBICZHAeCqEVBdkSMKT7Xe/KYCxiopLGgfQEgWQFEM8M9L1DAoSpuaLO7caTcLBGbmiu/lwstvVT7amQ2quRNZXk8mmB++lPV4v6l1FAhjj6OVXgUBbiFJ1ghxbaYh3sH5vpRgeLOv0Aakt4N6zXq+3W2czIGopXkR32XNmEugPNIYTtAypfrR+QnLioLK8FoPmttyqgvfKfiDHfkixzvqDaToVBE8EoxJsJckyd6PdyrHuITBkyBrHnscX5LMikjJze1KmRCLsko1DZ0/YlBKNZTbQ5NShlYibw5t7Phhv0T5pl+gsIUuPDlW7tMp1dIBx48oASuWNZfVyh5rfasRV9la9vHsZ6oB4ENNXyc+XpqYoKT8Hxn F8XDHOSM D+chldsVHHT4tA5MqaM3u4zQiq41T8/KHbDujxb096Nlr4y8lsOS62/wbJds3z/vinJIzG76kZy5rPy2KxgcfG4+vlovEduARdfNaUklcrT0M4MErBTUlWwzmW3iLg98s2039671QhzrpbUXgHGXDrNo0JLZ7uyzkE2SIohK0H3MtCphH0r2Ie0swbx30boDDyPN51cYy1v8e7s7wEwmhTomdQqFQxTyvtkY5PWouwZUjQZu504Fk1e7VsVjq5yFR1p/iPHxMLQjcsJYeJ5yc0zwC0FzBV5WaCjpGwsF8R5a2QFY= 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 Wed, Mar 22, 2023 at 10:39=E2=80=AFPM Huang, Ying = wrote: > > Yosry Ahmed writes: > > > On Wed, Mar 22, 2023 at 8:17=E2=80=AFPM Huang, Ying wrote: > >> > >> Yosry Ahmed writes: > >> > >> > On Wed, Mar 22, 2023 at 6:50=E2=80=AFPM Huang, Ying wrote: > >> >> > >> >> Yosry Ahmed writes: > >> >> > >> >> > On Sun, Mar 19, 2023 at 7:56=E2=80=AFPM Huang, Ying wrote: > >> >> >> > >> >> >> Yosry Ahmed writes: > >> >> >> > >> >> >> > On Thu, Mar 16, 2023 at 12:51=E2=80=AFAM Huang, Ying wrote: > >> >> >> >> > >> >> >> >> Yosry Ahmed writes: > >> >> >> >> > >> >> >> >> > On Sun, Mar 12, 2023 at 7:13=E2=80=AFPM Huang, Ying wrote: > >> >> >> >> >> > >> >> >> >> >> Yosry Ahmed writes: > >> >> >> >> >> > > [snip] > > >> >> > >> >> >> > >> >> >> >> > >> >> >> >> > >> >> >> >> > xarray (b) is indexed by swap id as well > >> >> >> >> > and contain swap entry or zswap entry. Reverse mapping migh= t be > >> >> >> >> > needed. > >> >> >> >> > >> >> >> >> Reverse mapping isn't needed. > >> >> >> > > >> >> >> > > >> >> >> > It would be needed if xarray (a) is indexed by the swap id. I = am not > >> >> >> > sure I understand how it can be indexed by the swap entry if t= he > >> >> >> > indirection is enabled. > >> >> >> > > >> >> >> >> > >> >> >> >> > >> >> >> >> > In this case we have an extra overhead of 12-16 bytes + 8 b= ytes for > >> >> >> >> > xarray (b) entry + memory overhead from 2nd xarray + revers= e mapping > >> >> >> >> > where needed. > >> >> >> >> > > >> >> >> >> > There is also the extra cpu overhead for an extra lookup in= certain paths. > >> >> >> >> > > >> >> >> >> > Is my analysis correct? If yes, I agree that the original p= roposal is > >> >> >> >> > good if the reverse mapping can be avoided in enough situat= ions, and > >> >> >> >> > that we should consider such alternatives otherwise. As I m= entioned > >> >> >> >> > above, I think it comes down to whether we can completely r= estrict > >> >> >> >> > cluster readahead to rotating disks or not -- in which case= we need to > >> >> >> >> > decide what to do for shmem and for anon when vma readahead= is > >> >> >> >> > disabled. > >> >> >> >> > >> >> >> >> We can even have a minimal indirection implementation. Where= , swap > >> >> >> >> cache and swap_map[] are kept as they ware before, just one x= array is > >> >> >> >> added. The xarray is indexed by swap id (or swap_desc index)= to store > >> >> >> >> the corresponding swap entry. > >> >> >> >> > >> >> >> >> When indirection is disabled, no extra overhead. > >> >> >> >> > >> >> >> >> When indirection is enabled, the extra overhead is just 8 byt= es per > >> >> >> >> swapped page. > >> >> >> >> > >> >> >> >> The basic migration support can be build on top of this. > >> >> >> >> > >> >> >> >> I think that this could be a baseline for indirection support= . Then > >> >> >> >> further optimization can be built on top of it step by step w= ith > >> >> >> >> supporting data. > >> >> >> > > >> >> >> > > >> >> >> > I am not sure how this works with zswap. Currently swap_map[] > >> >> >> > implementation is specific for swapfiles, it does not work for= zswap > >> >> >> > unless we implement separate swap counting logic for zswap & > >> >> >> > swapfiles. Same for the swapcache, it currently supports being= indexed > >> >> >> > by a swap entry, it would need to support being indexed by a s= wap id, > >> >> >> > or have a separate swap cache for zswap. Having separate > >> >> >> > implementation would add complexity, and we would need to perf= orm > >> >> >> > handoffs of the swap count/cache when a page is moved from zsw= ap to a > >> >> >> > swapfile. > >> >> >> > >> >> >> We can allocate a swap entry for each swapped page in zswap. > >> >> > > >> >> > > >> >> > This is exactly what the current implementation does and what we = want > >> >> > to move away from. The current implementation uses zswap as an > >> >> > in-memory compressed cache on top of an actual swap device, and e= ach > >> >> > swapped page in zswap has a swap entry allocated. With this > >> >> > implementation, zswap cannot be used without a swap device. > >> >> > >> >> I totally agree that we should avoid to use an actual swap device u= nder > >> >> zswap. And, as an swap implementation, zswap can manage the swap e= ntry > >> >> inside zswap without an underlying actual swap device. For example= , > >> >> when we swap a page to zswap (actually compress), we can allocate a > >> >> (virtual) swap entry in the zswap. I understand that there's overh= ead > >> >> to manage the swap entry in zswap. We can consider how to reduce t= he > >> >> overhead. > >> > > >> > I see. So we can (for example) use one of the swap types for zswap, > >> > and then have zswap code handle this entry according to its > >> > implementation. We can then have an xarray that maps swap ID -> swap > >> > entry, and this swap entry is used to index the swap cache and such. > >> > When a swapped page is moved between backends we update the swap ID = -> > >> > swap entry xarray. > >> > > >> > This is one possible implementation that I thought of (very briefly > >> > tbh), but it does have its problems: > >> > For zswap: > >> > - Managing swap entries inside zswap unnecessarily. > >> > - We need to maintain a swap entry -> zswap entry mapping in zswap -= - > >> > similar to the current rbtree, which is something that we can get ri= d > >> > of with the initial proposal if we embed the zswap_entry pointer > >> > directly in the swap_desc (it can be encoded to avoid breaking the > >> > abstraction). > >> > > >> > For mm/swap in general: > >> > - When we allocate a swap entry today, we store it in folio->private > >> > (or page->private), which is used by the unmapping code to be placed > >> > in the page tables or shmem page cache. With this implementation, we > >> > need to store the swap ID in page->private instead, which means that > >> > every time we need to access the swap cache during reclaim/swapout w= e > >> > need to lookup the swap entry first. > >> > - On the fault path, we need two lookups instead of one (swap ID -> > >> > swap entry, swap entry -> swap cache), not sure how this affects fau= lt > >> > latency. > >> > - Each swap backend will have its own separate implementation of swa= p > >> > counting, which is hard to maintain and very error-prone since the > >> > logic is backend-agnostic. > >> > - Handing over a page from one swap backend to another includes > >> > handing over swap cache entries and swap counts, which I imagine wil= l > >> > involve considerable synchronization. > >> > > >> > Do you have any thoughts on this? > >> > >> Yes. I understand there's additional overhead. I have no clear idea > >> about how to reduce this now. We need to think about that in depth. I agree that we need to think deeper about the tradeoff here. It seems like the extra xarray lookup may not be a huge problem, but there are other concerns such as having separate implementations of swap counting that are basically doing the same thing in different ways for different backends. > >> > >> The bottom line is whether this is worse than the current zswap > >> implementation? > > > > It's not just zswap, as I note above, this design would introduce some > > overheads to the core swapping code as well as long as the indirection > > layer is active. I am particularly worried about the extra lookups on > > the fault path. > > Maybe you can measure the time for the radix tree lookup? And compare > it with the total fault time? I ran a simple test with perf swapping in a 1G shmem file: |--1.91%--swap_cache_get_folio | | | --1.32%--__filemap_get_folio | | | --0.66%--xas_load Seems like the swap cache lookup is ~2%, and < 1% is coming from the xarray lookup. I am not sure if the lookup time varies a lot with fragmentation and different access patterns, but it seems like it's generally not a major contributor to the latency. > > > For zswap, we already have a lookup today, so maintaining swap entry > > -> zswap entry mapping would not be a regression, but I am not sure > > about the extra overhead to manage swap entries within zswap. Keep in > > mind that using swap entries for zswap probably implies having a > > fixed/max size for zswap (to be able to manage the swap entries > > efficiently similar to swap devices), which is a limitation that the > > initial proposal was hoping to overcome. > > We have limited bits in PTE, so the max number of zswap entries will be > limited anyway. And, we don't need to manage swap entries in the same > way as disks (which need to consider sequential writing etc.). Right, the number of bits allowed would impose a maximum on the swap ID, which would imply a maximum on the number of zswap entries. The concern is about managing swap entries within zswap. If zswap needs to keep track of the entries it allocated and the entries that are free, it needs a data structure to do so (e.g. a bitmap). The size of this data structure can potentially scale with the maximum number of entries, so we would want to impose a virtual limit on zswap entries to limit the size of the data structure. Alternatively, we can have a dynamic data structure, but this also comes with its complexities. > > Best Regards, > Huang, Ying > > [snip] >