Re: [LSF/MM/BPF TOPIC] Swap Abstraction / Native Zswap

[Yosry Ahmed <yosryahmed@google.com>]

On Thu, Mar 16, 2023 at 12:51 AM Huang, Ying <ying.huang@intel.com> wrote:
>
> Yosry Ahmed <yosryahmed@google.com> writes:
>
> > On Sun, Mar 12, 2023 at 7:13 PM Huang, Ying <ying.huang@intel.com> wrote:
> >>
> >> Yosry Ahmed <yosryahmed@google.com> writes:
> >>
> >> <snip>
> >> >
> >> > My current idea is to have one xarray that stores the swap_descs
> >> > (which include swap_entry, swapcache, swap_count, etc), and only for
> >> > rotating disks have an additional xarray that maps swap_entry ->
> >> > swap_desc for cluster readahead, assuming we can eliminate all other
> >> > situations requiring a reverse mapping.
> >> >
> >> > I am not sure how having separate xarrays help? If we have one xarray,
> >> > might as well save the other lookups on put everything in swap_desc.
> >> > In fact, this should improve the locking today as swapcache /
> >> > swap_count operations can be lockless or very lightly contended.
> >>
> >> The condition of the proposal is "reverse mapping cannot be avoided for
> >> enough situation".  So, if reverse mapping (or cluster readahead) can be
> >> avoided for enough situations, I think your proposal is good.  Otherwise,
> >> I propose to use 2 xarrays.  You don't need another reverse mapping
> >> xarray, because you just need to read the next several swap_entry into
> >> the swap cache for cluster readahead.  swap_desc isn't needed for
> >> cluster readahead.
> >
> > swap_desc would be needed for cluster readahead in my original
> > proposal as the swap cache lives in swap_descs. Based on the current
> > implementation, we would need a reverse mapping (swap entry ->
> > swap_desc) in 3 situations:
> >
> > 1) __try_to_reclaim_swap(): when trying to find an empty swap slot and
> > failing, we fallback to trying to find swap entries that only have a
> > page in the swap cache (no references in page tables or page cache)
> > and free them. This would require a reverse mapping.
> >
> > 2) swapoff: we need to swap in all entries in a swapfile, so we need
> > to get all swap_descs associated with that swapfile.
> >
> > 3) swap cluster readahead.
> >
> > For (1), I think we can drop the dependency of a reverse mapping if we
> > free swap entries once we swap a page in and add it to the swap cache,
> > even if the swap count does not drop to 0.
>
> Now, we will not drop the swap cache even if the swap count becomes 0 if
> swap space utility < 50%.  Per my understanding, this avoid swap page
> writing for read accesses.  So I don't think we can change this directly
> without necessary discussion firstly.


Right. I am not sure I understand why we do this today, is it to save
the overhead of allocating a new swap entry if the page is swapped out
again soon? I am not sure I understand this statement "this avoid swap
page
writing for read accesses".

>
>
> > For (2), instead of scanning page tables and shmem page cache to find
> > swapped out pages for the swapfile, we can scan all swap_descs
> > instead, we should be more efficient. This is one of the proposal's
> > potential advantages.
>
> Good.
>
> > (3) is the one that would still need a reverse mapping with the
> > current proposal. Today we use swap cluster readahead for anon pages
> > if we have a spinning disk or vma readahead is disabled. For shmem, we
> > always use cluster readahead. If we can limit cluster readahead to
> > only rotating disks, then the reverse mapping can only be maintained
> > for swapfiles on rotating disks. Otherwise, we will need to maintain a
> > reverse mapping for all swapfiles.
>
> For shmem, I think that it should be good to readahead based on shmem
> file offset instead of swap device offset.
>
> It's possible that some pages in the readahead window are from HDD while
> some other pages aren't.  So it's a little hard to enable cluster read
> for HDD only.  Anyway, it's not common to use HDD for swap now.
>
> >>
> >> > If the point is to store the swap_desc directly inside the xarray to
> >> > save 8 bytes, I am concerned that having multiple xarrays for
> >> > swapcache, swap_count, etc will use more than that.
> >>
> >> The idea is to save the memory used by reverse mapping xarray.
> >
> > I see.
> >
> >>
> >> >> >>
> >> >> >> > Keep in mind that the current overhead is 1 byte O(max swap pages) not
> >> >> >> > O(swapped). Also, 1 byte is assuming we do not use the swap
> >> >> >> > continuation pages. If we do, it may end up being more. We also
> >> >> >> > allocate continuation in full 4k pages, so even if one swap_map
> >> >> >> > element in a page requires continuation, we will allocate an entire
> >> >> >> > page. What I am trying to say is that to get an actual comparison you
> >> >> >> > need to also factor in the swap utilization and the rate of usage of
> >> >> >> > swap continuation. I don't know how to come up with a formula for this
> >> >> >> > tbh.
> >> >> >> >
> >> >> >> > Also, like Johannes said, the worst case overhead (32 bytes if you
> >> >> >> > count the reverse mapping) is 0.8% of swapped memory, aka 8M for every
> >> >> >> > 1G swapped. It doesn't sound *very* bad. I understand that it is pure
> >> >> >> > overhead for people not using zswap, but it is not very awful.
> >> >> >> >
> >> >> >> >>
> >> >> >> >> It seems what you really need is one bit of information to indicate
> >> >> >> >> this page is backed by zswap. Then you can have a seperate pointer
> >> >> >> >> for the zswap entry.
> >> >> >> >
> >> >> >> > If you use one bit in swp_entry_t (or one of the available swap types)
> >> >> >> > to indicate whether the page is backed with a swapfile or zswap it
> >> >> >> > doesn't really work. We lose the indirection layer. How do we move the
> >> >> >> > page from zswap to swapfile? We need to go update the page tables and
> >> >> >> > the shmem page cache, similar to swapoff.
> >> >> >> >
> >> >> >> > Instead, if we store a key else in swp_entry_t and use this to lookup
> >> >> >> > the swp_entry_t or zswap_entry pointer then that's essentially what
> >> >> >> > the swap_desc does. It just goes the extra mile of unifying the
> >> >> >> > swapcache as well and storing it directly in the swap_desc instead of
> >> >> >> > storing it in another lookup structure.
> >> >> >>
> >> >> >> If we choose to make sizeof(struct swap_desc) == 8, that is, store only
> >> >> >> swap_entry in swap_desc.  The added indirection appears to be another
> >> >> >> level of page table with 1 entry.  Then, we may use the similar method
> >> >> >> as supporting system with 2 level and 3 level page tables, like the code
> >> >> >> in include/asm-generic/pgtable-nopmd.h.  But I haven't thought about
> >> >> >> this deeply.
> >> >> >
> >> >> > Can you expand further on this idea? I am not sure I fully understand.
> >> >>
> >> >> OK.  The goal is to avoid the overhead if indirection isn't enabled via
> >> >> kconfig.
> >> >>
> >> >> If indirection isn't enabled, store swap_entry in PTE directly.
> >> >> Otherwise, store index of swap_desc in PTE.  Different functions (e.g.,
> >> >> to get/set swap_entry in PTE) are implemented based on kconfig.
> >> >
> >> >
> >> > I thought about this, the problem is that we will have multiple
> >> > implementations of multiple things. For example, swap_count without
> >> > the indirection layer lives in the swap_map (with continuation logic).
> >> > With the indirection layer, it lives in the swap_desc (or somewhere
> >> > else). Same for the swapcache. Even if we keep the swapcache in an
> >> > xarray and not inside swap_desc, it would be indexed by swap_entry if
> >> > the indirection is disabled, and by swap_desc (or similar) if the
> >> > indirection is enabled. I think maintaining separate implementations
> >> > for when the indirection is enabled/disabled would be adding too much
> >> > complexity.
> >> >
> >> > WDYT?
> >>
> >> If we go this way, swap cache and swap_count will always be indexed by
> >> swap_entry.  swap_desc just provides a indirection to make it possible
> >> to move between swap devices.
> >>
> >> Why must we index swap cache and swap_count by swap_desc if indirection
> >> is enabled?  Yes, we can save one xarray indexing if we do so, but I
> >> don't think the overhead of one xarray indexing is a showstopper.
> >>
> >> I think this can be one intermediate step towards your final target.
> >> The changes to current implementation can be smaller.
> >
> > IIUC, the idea is to have two xarrays:
> > (a) xarray that stores a pointer to a struct containing swap_count and
> > swap cache.
> > (b) xarray that stores the underlying swap entry or zswap entry.
> >
> > When indirection is disabled:
> > page tables & page cache have swap entry directly like today, xarray
> > (a) is indexed by swap entry, xarray (b) does not exist. No reverse
> > mapping needed.
> >
> > In this case we have an extra overhead of 12-16 bytes (the struct
> > containing swap_count and swap cache) vs. 24 bytes of the swap_desc.
> >
> > When indirection is enabled:
> > page tables & page cache have a swap id (or swap_desc index), xarray
> > (a) is indexed by swap id,
>
> xarray (a) is indexed by swap entry.


How so? With the indirection enabled, the page tables & page cache
have the swap id (or swap_desc index), which can point to a swap entry
or a zswap entry -- which can change when the page is moved between
zswap & swapfiles. How is xarray (a) indexed by the swap entry in this
case? Shouldn't be indexed by the abstract swap id so that the
writeback from zswap is transparent?

>
>
> > xarray (b) is indexed by swap id as well
> > and contain swap entry or zswap entry. Reverse mapping might 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 the
indirection is enabled.

>
>
> > In this case we have an extra overhead of 12-16 bytes + 8 bytes for
> > xarray (b) entry + memory overhead from 2nd xarray + reverse 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 proposal is
> > good if the reverse mapping can be avoided in enough situations, and
> > that we should consider such alternatives otherwise. As I mentioned
> > above, I think it comes down to whether we can completely restrict
> > 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 xarray 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 bytes 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 with
> 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 swap id,
or have a separate swap cache for zswap. Having separate
implementation would add complexity, and we would need to perform
handoffs of the swap count/cache when a page is moved from zswap to a
swapfile.

>
>
> >>
> >> >> >> >>
> >> >> >> >> Depending on how much you are going to reuse the swap cache, you might
> >> >> >> >> need to have something like a swap_info_struct to keep the locks happy.
> >> >> >> >
> >> >> >> > My current intention is to reimplement the swapcache completely as a
> >> >> >> > pointer in struct swap_desc. This would eliminate this need and a lot
> >> >> >> > of the locking we do today if I get things right.
> >> >> >> >
> >> >> >> >>
> >> >> >> >> > Another potential concern is readahead. With this design, we have no
> >> >> >> >>
> >> >> >> >> Readahead is for spinning disk :-) Even a normal swap file with an SSD can
> >> >> >> >> use some modernization.
> >> >> >> >
> >> >> >> > Yeah, I initially thought we would only need the swp_entry_t ->
> >> >> >> > swap_desc reverse mapping for readahead, and that we can only store
> >> >> >> > that for spinning disks, but I was wrong. We need for other things as
> >> >> >> > well today: swapoff, when trying to find an empty swap slot and we
> >> >> >> > start trying to free swap slots used only by the swapcache. However, I
> >> >> >> > think both of these cases can be fixed (I can share more details if
> >> >> >> > you want). If everything goes well we should only need to maintain the
> >> >> >> > reverse mapping (extra overhead above 24 bytes) for swap files on
> >> >> >> > spinning disks for readahead.
> >> >> >> >
> >> >> >> >>
> >> >> >> >> Looking forward to your discussion.
> >> >>
> >> >> Per my understanding, the indirection is to make it easy to move
> >> >> (swapped) pages among swap devices based on hot/cold.  This is similar
> >> >> as the target of memory tiering.  It appears that we can extend the
> >> >> memory tiering (mm/memory-tiers.c) framework to cover swap devices too?
> >> >> Is it possible for zswap to be faster than some slow memory media?
> >> >
> >> >
> >> > Agree with Chris that this may require a much larger overhaul. A slow
> >> > memory tier is still addressable memory, swap/zswap requires a page
> >> > fault to read the pages. I think (at least for now) there is a
> >> > fundamental difference. We want reclaim to eventually treat slow
> >> > memory & swap as just different tiers to place cold memory in with
> >> > different characteristics, but otherwise I think the swapping
> >> > implementation itself is very different.  Am I missing something?
> >>
> >> Is it possible that zswap is faster than a really slow memory
> >> addressable device backed by NAND?  TBH, I don't have the answer.
> >
> > I am not sure either.
> >
> >>
> >> Anyway, do you need a way to describe the tiers of the swap devices?
> >> So, you can move the cold pages among the swap devices based on that?
> >
> > For now I think the "tiers" in this proposal are just zswap and normal
> > swapfiles. We can later extend it to support more explicit tiering.
>
> IIUC, in original zswap implementation, there's 1:1 relationship between
> zswap and normal swapfile.  But now, you make demoting among swap
> devices more general.  Then we need some general way to specify which
> swap devices are fast and which are slow, and the demoting relationship
> among them.  It can be memory tiers or something else, but we need one.


I think for this proposal, there are only 2 hardcoded tiers. Zswap is
fast, swapfile is slow. In the future, we can support more dynamic
tiering if the need arises.

>
>
> Best Regards,
> Huang, Ying
>