On Wed, Mar 22, 2023 at 10:39 PM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
>
> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
>
> > On Wed, Mar 22, 2023 at 8:17 PM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
> >>
> >> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
> >>
> >> > On Wed, Mar 22, 2023 at 6:50 PM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
> >> >>
> >> >> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
> >> >>
> >> >> > On Sun, Mar 19, 2023 at 7:56 PM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
> >> >> >>
> >> >> >> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
> >> >> >>
> >> >> >> > On Thu, Mar 16, 2023 at 12:51 AM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
> >> >> >> >>
> >> >> >> >> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
> >> >> >> >>
> >> >> >> >> > On Sun, Mar 12, 2023 at 7:13 PM Huang, Ying <ying.huang@xxxxxxxxx> wrote:
> >> >> >> >> >>
> >> >> >> >> >> Yosry Ahmed <yosryahmed@xxxxxxxxxx> writes:
> >> >> >> >> >>
>
> [snip]
>
> >> >>
> >> >> >>
> >> >> >> >>
> >> >> >> >>
> >> >> >> >> > 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.
> >> >> >>
> >> >> >> 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 each
> >> >> > 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 under
> >> >> zswap. And, as an swap implementation, zswap can manage the swap entry
> >> >> 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 overhead
> >> >> to manage the swap entry in zswap. We can consider how to reduce the
> >> >> 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 rid
> >> > 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 we
> >> > 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 fault
> >> > latency.
> >> > - Each swap backend will have its own separate implementation of swap
> >> > 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 will
> >> > 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]
>
