[RFC,6/9] mm: zswap: drop support for non-zero same-filled pages handling

Commit Message

Yosry Ahmed March 25, 2024, 11:50 p.m. UTC

The current same-filled pages handling supports pages filled with any
repeated word-sized pattern. However, in practice, most of these should
be zero pages anyway. Other patterns should be nearly as common.

Drop the support for non-zero same-filled pages, but keep the names of
knobs exposed to userspace as "same_filled", which isn't entirely
inaccurate.

This yields some nice code simplification and enables a following patch
that eliminates the need to allocate struct zswap_entry for those pages
completely.

There is also a very small performance improvement observed over 50 runs
of kernel build test (kernbench) comparing the mean build time on a
skylake machine when building the kernel in a cgroup v1 container with a
3G limit:

		base		patched		% diff
real		70.167		69.915		-0.359%
user		2953.068	2956.147	+0.104%
sys		2612.811	2594.718	-0.692%

This probably comes from more optimized operations like memchr_inv() and
clear_highpage(). Note that the percentage of zero-filled pages during
this test was only around 1.5% on average, and was not affected by this
patch. Practical workloads could have a larger proportion of such pages
(e.g. Johannes observed around 10% [1]), so the performance improvement
should be larger.

[1]https://lore.kernel.org/linux-mm/[e-mail]/

Signed-off-by: Yosry Ahmed <[e-mail]>
---
 mm/zswap.c | 76 ++++++++++++++----------------------------------------
 1 file changed, 20 insertions(+), 56 deletions(-)

Comments

Chengming Zhou March 27, 2024, 11:25 a.m. UTC | #1

On 2024/3/26 07:50, Yosry Ahmed wrote:
> The current same-filled pages handling supports pages filled with any
> repeated word-sized pattern. However, in practice, most of these should
> be zero pages anyway. Other patterns should be nearly as common.
> 
> Drop the support for non-zero same-filled pages, but keep the names of
> knobs exposed to userspace as "same_filled", which isn't entirely
> inaccurate.
> 
> This yields some nice code simplification and enables a following patch
> that eliminates the need to allocate struct zswap_entry for those pages
> completely.
> 
> There is also a very small performance improvement observed over 50 runs
> of kernel build test (kernbench) comparing the mean build time on a
> skylake machine when building the kernel in a cgroup v1 container with a
> 3G limit:
> 
> 		base		patched		% diff
> real		70.167		69.915		-0.359%
> user		2953.068	2956.147	+0.104%
> sys		2612.811	2594.718	-0.692%
> 
> This probably comes from more optimized operations like memchr_inv() and
> clear_highpage(). Note that the percentage of zero-filled pages during
> this test was only around 1.5% on average, and was not affected by this
> patch. Practical workloads could have a larger proportion of such pages
> (e.g. Johannes observed around 10% [1]), so the performance improvement
> should be larger.
> 
> [1]https://lore.kernel.org/linux-mm/[e-mail]/
> 
> Signed-off-by: Yosry Ahmed <[e-mail]>

The code looks good!

Reviewed-by: Chengming Zhou <[e-mail]>

Thanks.

> ---
>  mm/zswap.c | 76 ++++++++++++++----------------------------------------
>  1 file changed, 20 insertions(+), 56 deletions(-)
> 
> diff --git a/mm/zswap.c b/mm/zswap.c
> index 0fc27ae950c74..413d9242cf500 100644
> --- a/mm/zswap.c
> +++ b/mm/zswap.c
> @@ -44,8 +44,8 @@
>  **********************************/
>  /* The number of compressed pages currently stored in zswap */
>  atomic_t zswap_stored_pages = ATOMIC_INIT(0);
> -/* The number of same-value filled pages currently stored in zswap */
> -static atomic_t zswap_same_filled_pages = ATOMIC_INIT(0);
> +/* The number of zero-filled pages currently stored in zswap */
> +static atomic_t zswap_zero_filled_pages = ATOMIC_INIT(0);
>  
>  /*
>   * The statistics below are not protected from concurrent access for
> @@ -123,9 +123,9 @@ static unsigned int zswap_accept_thr_percent = 90; /* of max pool size */
>  module_param_named(accept_threshold_percent, zswap_accept_thr_percent,
>  		   uint, 0644);
>  
> -/* Enable/disable handling non-same-value filled pages (enabled by default) */
> -static bool zswap_non_same_filled_pages_enabled = true;
> -module_param_named(non_same_filled_pages_enabled, zswap_non_same_filled_pages_enabled,
> +/* Enable/disable handling non-zero-filled pages (enabled by default) */
> +static bool zswap_non_zero_filled_pages_enabled = true;
> +module_param_named(non_same_filled_pages_enabled, zswap_non_zero_filled_pages_enabled,
>  		   bool, 0644);
>  
>  /* Number of zpools in zswap_pool (empirically determined for scalability) */
> @@ -187,11 +187,10 @@ static struct shrinker *zswap_shrinker;
>   *
>   * swpentry - associated swap entry, the offset indexes into the red-black tree
>   * length - the length in bytes of the compressed page data.  Needed during
> - *          decompression. For a same value filled page length is 0, and both
> + *          decompression. For a zero-filled page length is 0, and both
>   *          pool and lru are invalid and must be ignored.
>   * pool - the zswap_pool the entry's data is in
>   * handle - zpool allocation handle that stores the compressed page data
> - * value - value of the same-value filled pages which have same content
>   * objcg - the obj_cgroup that the compressed memory is charged to
>   * lru - handle to the pool's lru used to evict pages.
>   */
> @@ -199,10 +198,7 @@ struct zswap_entry {
>  	swp_entry_t swpentry;
>  	unsigned int length;
>  	struct zswap_pool *pool;
> -	union {
> -		unsigned long handle;
> -		unsigned long value;
> -	};
> +	unsigned long handle;
>  	struct obj_cgroup *objcg;
>  	struct list_head lru;
>  };
> @@ -805,7 +801,7 @@ static struct zpool *zswap_find_zpool(struct zswap_entry *entry)
>  static void zswap_entry_free(struct zswap_entry *entry)
>  {
>  	if (!entry->length)
> -		atomic_dec(&zswap_same_filled_pages);
> +		atomic_dec(&zswap_zero_filled_pages);
>  	else {
>  		zswap_lru_del(&zswap_list_lru, entry);
>  		zpool_free(zswap_find_zpool(entry), entry->handle);
> @@ -1377,43 +1373,17 @@ static void shrink_worker(struct work_struct *w)
>  	} while (zswap_total_pages() > thr);
>  }
>  
> -static bool zswap_is_folio_same_filled(struct folio *folio, unsigned long *value)
> +static bool zswap_is_folio_zero_filled(struct folio *folio)
>  {
> -	unsigned long *page;
> -	unsigned long val;
> -	unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1;
> +	unsigned long *kaddr;
>  	bool ret;
>  
> -	page = kmap_local_folio(folio, 0);
> -	val = page[0];
> -
> -	if (val != page[last_pos]) {
> -		ret = false;
> -		goto out;
> -	}
> -
> -	for (pos = 1; pos < last_pos; pos++) {
> -		if (val != page[pos]) {
> -			ret = false;
> -			goto out;
> -		}
> -	}
> -
> -	*value = val;
> -	ret = true;
> -out:
> -	kunmap_local(page);
> +	kaddr = kmap_local_folio(folio, 0);
> +	ret = !memchr_inv(kaddr, 0, PAGE_SIZE);
> +	kunmap_local(kaddr);
>  	return ret;
>  }
>  
> -static void zswap_fill_page(void *ptr, unsigned long value)
> -{
> -	unsigned long *page;
> -
> -	page = (unsigned long *)ptr;
> -	memset_l(page, value, PAGE_SIZE / sizeof(unsigned long));
> -}
> -
>  static bool zswap_check_limit(void)
>  {
>  	unsigned long cur_pages = zswap_total_pages();
> @@ -1437,7 +1407,6 @@ bool zswap_store(struct folio *folio)
>  	struct obj_cgroup *objcg = NULL;
>  	struct mem_cgroup *memcg = NULL;
>  	struct zswap_entry *entry;
> -	unsigned long value;
>  
>  	VM_WARN_ON_ONCE(!folio_test_locked(folio));
>  	VM_WARN_ON_ONCE(!folio_test_swapcache(folio));
> @@ -1470,14 +1439,13 @@ bool zswap_store(struct folio *folio)
>  		goto reject;
>  	}
>  
> -	if (zswap_is_folio_same_filled(folio, &value)) {
> +	if (zswap_is_folio_zero_filled(folio)) {
>  		entry->length = 0;
> -		entry->value = value;
> -		atomic_inc(&zswap_same_filled_pages);
> +		atomic_inc(&zswap_zero_filled_pages);
>  		goto insert_entry;
>  	}
>  
> -	if (!zswap_non_same_filled_pages_enabled)
> +	if (!zswap_non_zero_filled_pages_enabled)
>  		goto freepage;
>  
>  	/* if entry is successfully added, it keeps the reference */
> @@ -1532,7 +1500,7 @@ bool zswap_store(struct folio *folio)
>  
>  store_failed:
>  	if (!entry->length)
> -		atomic_dec(&zswap_same_filled_pages);
> +		atomic_dec(&zswap_zero_filled_pages);
>  	else {
>  		zpool_free(zswap_find_zpool(entry), entry->handle);
>  put_pool:
> @@ -1563,7 +1531,6 @@ bool zswap_load(struct folio *folio)
>  	struct page *page = &folio->page;
>  	struct xarray *tree = swap_zswap_tree(swp);
>  	struct zswap_entry *entry;
> -	u8 *dst;
>  
>  	VM_WARN_ON_ONCE(!folio_test_locked(folio));
>  
> @@ -1573,11 +1540,8 @@ bool zswap_load(struct folio *folio)
>  
>  	if (entry->length)
>  		zswap_decompress(entry, page);
> -	else {
> -		dst = kmap_local_page(page);
> -		zswap_fill_page(dst, entry->value);
> -		kunmap_local(dst);
> -	}
> +	else
> +		clear_highpage(page);
>  
>  	count_vm_event(ZSWPIN);
>  	if (entry->objcg)
> @@ -1679,7 +1643,7 @@ static int zswap_debugfs_init(void)
>  	debugfs_create_atomic_t("stored_pages", 0444,
>  				zswap_debugfs_root, &zswap_stored_pages);
>  	debugfs_create_atomic_t("same_filled_pages", 0444,
> -				zswap_debugfs_root, &zswap_same_filled_pages);
> +				zswap_debugfs_root, &zswap_zero_filled_pages);
>  
>  	return 0;
>  }

Nhat Pham March 27, 2024, 4:40 p.m. UTC | #2

On Mon, Mar 25, 2024 at 4:50 PM Yosry Ahmed <[e-mail]> wrote:
>
> The current same-filled pages handling supports pages filled with any
> repeated word-sized pattern. However, in practice, most of these should
> be zero pages anyway. Other patterns should be nearly as common.

It'd be nice if we can verify this somehow. Maybe hooking bpftrace,
trace_printk, etc. here?

That aside, my intuition is that this is correct too. It's much less
likely to see a non-zero filled page.

>
> Drop the support for non-zero same-filled pages, but keep the names of
> knobs exposed to userspace as "same_filled", which isn't entirely
> inaccurate.
>
> This yields some nice code simplification and enables a following patch
> that eliminates the need to allocate struct zswap_entry for those pages
> completely.
>
> There is also a very small performance improvement observed over 50 runs
> of kernel build test (kernbench) comparing the mean build time on a
> skylake machine when building the kernel in a cgroup v1 container with a
> 3G limit:
>
>                 base            patched         % diff
> real            70.167          69.915          -0.359%
> user            2953.068        2956.147        +0.104%
> sys             2612.811        2594.718        -0.692%
>
> This probably comes from more optimized operations like memchr_inv() and
> clear_highpage(). Note that the percentage of zero-filled pages during

TIL clear_highpage() is a thing :)


> this test was only around 1.5% on average, and was not affected by this
> patch. Practical workloads could have a larger proportion of such pages
> (e.g. Johannes observed around 10% [1]), so the performance improvement
> should be larger.
>
> [1]https://lore.kernel.org/linux-mm/[e-mail]/
>
> Signed-off-by: Yosry Ahmed <[e-mail]>
> ---
>  mm/zswap.c | 76 ++++++++++++++----------------------------------------
>  1 file changed, 20 insertions(+), 56 deletions(-)
>
> diff --git a/mm/zswap.c b/mm/zswap.c
> index 0fc27ae950c74..413d9242cf500 100644
> --- a/mm/zswap.c
> +++ b/mm/zswap.c
> @@ -44,8 +44,8 @@
>  **********************************/
>  /* The number of compressed pages currently stored in zswap */
>  atomic_t zswap_stored_pages = ATOMIC_INIT(0);
> -/* The number of same-value filled pages currently stored in zswap */
> -static atomic_t zswap_same_filled_pages = ATOMIC_INIT(0);
> +/* The number of zero-filled pages currently stored in zswap */
> +static atomic_t zswap_zero_filled_pages = ATOMIC_INIT(0);
>
>  /*
>   * The statistics below are not protected from concurrent access for
> @@ -123,9 +123,9 @@ static unsigned int zswap_accept_thr_percent = 90; /* of max pool size */
>  module_param_named(accept_threshold_percent, zswap_accept_thr_percent,
>                    uint, 0644);
>
> -/* Enable/disable handling non-same-value filled pages (enabled by default) */
> -static bool zswap_non_same_filled_pages_enabled = true;
> -module_param_named(non_same_filled_pages_enabled, zswap_non_same_filled_pages_enabled,
> +/* Enable/disable handling non-zero-filled pages (enabled by default) */
> +static bool zswap_non_zero_filled_pages_enabled = true;
> +module_param_named(non_same_filled_pages_enabled, zswap_non_zero_filled_pages_enabled,
>                    bool, 0644);
>
>  /* Number of zpools in zswap_pool (empirically determined for scalability) */
> @@ -187,11 +187,10 @@ static struct shrinker *zswap_shrinker;
>   *
>   * swpentry - associated swap entry, the offset indexes into the red-black tree
>   * length - the length in bytes of the compressed page data.  Needed during
> - *          decompression. For a same value filled page length is 0, and both
> + *          decompression. For a zero-filled page length is 0, and both
>   *          pool and lru are invalid and must be ignored.
>   * pool - the zswap_pool the entry's data is in
>   * handle - zpool allocation handle that stores the compressed page data
> - * value - value of the same-value filled pages which have same content
>   * objcg - the obj_cgroup that the compressed memory is charged to
>   * lru - handle to the pool's lru used to evict pages.
>   */
> @@ -199,10 +198,7 @@ struct zswap_entry {
>         swp_entry_t swpentry;
>         unsigned int length;
>         struct zswap_pool *pool;
> -       union {
> -               unsigned long handle;
> -               unsigned long value;
> -       };
> +       unsigned long handle;
>         struct obj_cgroup *objcg;
>         struct list_head lru;
>  };
> @@ -805,7 +801,7 @@ static struct zpool *zswap_find_zpool(struct zswap_entry *entry)
>  static void zswap_entry_free(struct zswap_entry *entry)
>  {
>         if (!entry->length)
> -               atomic_dec(&zswap_same_filled_pages);
> +               atomic_dec(&zswap_zero_filled_pages);
>         else {
>                 zswap_lru_del(&zswap_list_lru, entry);
>                 zpool_free(zswap_find_zpool(entry), entry->handle);
> @@ -1377,43 +1373,17 @@ static void shrink_worker(struct work_struct *w)
>         } while (zswap_total_pages() > thr);
>  }
>
> -static bool zswap_is_folio_same_filled(struct folio *folio, unsigned long *value)
> +static bool zswap_is_folio_zero_filled(struct folio *folio)
>  {
> -       unsigned long *page;
> -       unsigned long val;
> -       unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1;
> +       unsigned long *kaddr;
>         bool ret;
>
> -       page = kmap_local_folio(folio, 0);
> -       val = page[0];
> -
> -       if (val != page[last_pos]) {
> -               ret = false;
> -               goto out;
> -       }
> -
> -       for (pos = 1; pos < last_pos; pos++) {
> -               if (val != page[pos]) {
> -                       ret = false;
> -                       goto out;
> -               }
> -       }
> -
> -       *value = val;
> -       ret = true;
> -out:
> -       kunmap_local(page);
> +       kaddr = kmap_local_folio(folio, 0);
> +       ret = !memchr_inv(kaddr, 0, PAGE_SIZE);
> +       kunmap_local(kaddr);
>         return ret;
>  }
>
> -static void zswap_fill_page(void *ptr, unsigned long value)
> -{
> -       unsigned long *page;
> -
> -       page = (unsigned long *)ptr;
> -       memset_l(page, value, PAGE_SIZE / sizeof(unsigned long));
> -}
> -
>  static bool zswap_check_limit(void)
>  {
>         unsigned long cur_pages = zswap_total_pages();
> @@ -1437,7 +1407,6 @@ bool zswap_store(struct folio *folio)
>         struct obj_cgroup *objcg = NULL;
>         struct mem_cgroup *memcg = NULL;
>         struct zswap_entry *entry;
> -       unsigned long value;
>
>         VM_WARN_ON_ONCE(!folio_test_locked(folio));
>         VM_WARN_ON_ONCE(!folio_test_swapcache(folio));
> @@ -1470,14 +1439,13 @@ bool zswap_store(struct folio *folio)
>                 goto reject;
>         }
>
> -       if (zswap_is_folio_same_filled(folio, &value)) {
> +       if (zswap_is_folio_zero_filled(folio)) {
>                 entry->length = 0;
> -               entry->value = value;
> -               atomic_inc(&zswap_same_filled_pages);
> +               atomic_inc(&zswap_zero_filled_pages);
>                 goto insert_entry;
>         }
>
> -       if (!zswap_non_same_filled_pages_enabled)
> +       if (!zswap_non_zero_filled_pages_enabled)
>                 goto freepage;
>
>         /* if entry is successfully added, it keeps the reference */
> @@ -1532,7 +1500,7 @@ bool zswap_store(struct folio *folio)
>
>  store_failed:
>         if (!entry->length)
> -               atomic_dec(&zswap_same_filled_pages);
> +               atomic_dec(&zswap_zero_filled_pages);
>         else {
>                 zpool_free(zswap_find_zpool(entry), entry->handle);
>  put_pool:
> @@ -1563,7 +1531,6 @@ bool zswap_load(struct folio *folio)
>         struct page *page = &folio->page;
>         struct xarray *tree = swap_zswap_tree(swp);
>         struct zswap_entry *entry;
> -       u8 *dst;
>
>         VM_WARN_ON_ONCE(!folio_test_locked(folio));
>
> @@ -1573,11 +1540,8 @@ bool zswap_load(struct folio *folio)
>
>         if (entry->length)
>                 zswap_decompress(entry, page);
> -       else {
> -               dst = kmap_local_page(page);
> -               zswap_fill_page(dst, entry->value);
> -               kunmap_local(dst);
> -       }
> +       else
> +               clear_highpage(page);
>
>         count_vm_event(ZSWPIN);
>         if (entry->objcg)
> @@ -1679,7 +1643,7 @@ static int zswap_debugfs_init(void)
>         debugfs_create_atomic_t("stored_pages", 0444,
>                                 zswap_debugfs_root, &zswap_stored_pages);
>         debugfs_create_atomic_t("same_filled_pages", 0444,
> -                               zswap_debugfs_root, &zswap_same_filled_pages);
> +                               zswap_debugfs_root, &zswap_zero_filled_pages);
>
>         return 0;
>  }
> --
> 2.44.0.396.g6e790dbe36-goog
>

The code itself LGTM, FWIW:

Reviewed-by: Nhat Pham <[e-mail]>

Yosry Ahmed March 27, 2024, 10:38 p.m. UTC | #3

On Wed, Mar 27, 2024 at 9:41 AM Nhat Pham <[e-mail]> wrote:
>
> On Mon, Mar 25, 2024 at 4:50 PM Yosry Ahmed <[e-mail]> wrote:
> >
> > The current same-filled pages handling supports pages filled with any
> > repeated word-sized pattern. However, in practice, most of these should
> > be zero pages anyway. Other patterns should be nearly as common.
>
> It'd be nice if we can verify this somehow. Maybe hooking bpftrace,
> trace_printk, etc. here?

I am trying to do that. Unfortunately collecting this data from our
fleet is not easy, so it will take some time to figure out. If the
data happens to be easy-ish to collect from your fleet that would be
awesome :)

>
> That aside, my intuition is that this is correct too. It's much less
> likely to see a non-zero filled page.
>
> >
> > Drop the support for non-zero same-filled pages, but keep the names of
> > knobs exposed to userspace as "same_filled", which isn't entirely
> > inaccurate.
> >
> > This yields some nice code simplification and enables a following patch
> > that eliminates the need to allocate struct zswap_entry for those pages
> > completely.
> >
> > There is also a very small performance improvement observed over 50 runs
> > of kernel build test (kernbench) comparing the mean build time on a
> > skylake machine when building the kernel in a cgroup v1 container with a
> > 3G limit:
> >
> >                 base            patched         % diff
> > real            70.167          69.915          -0.359%
> > user            2953.068        2956.147        +0.104%
> > sys             2612.811        2594.718        -0.692%
> >
> > This probably comes from more optimized operations like memchr_inv() and
> > clear_highpage(). Note that the percentage of zero-filled pages during
>
> TIL clear_highpage() is a thing :)
>
>
[..]
>
> The code itself LGTM, FWIW:
>
> Reviewed-by: Nhat Pham <[e-mail]>

Thanks!

Johannes Weiner March 28, 2024, 7:31 p.m. UTC | #4

On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> The current same-filled pages handling supports pages filled with any
> repeated word-sized pattern. However, in practice, most of these should
> be zero pages anyway. Other patterns should be nearly as common.
> 
> Drop the support for non-zero same-filled pages, but keep the names of
> knobs exposed to userspace as "same_filled", which isn't entirely
> inaccurate.
> 
> This yields some nice code simplification and enables a following patch
> that eliminates the need to allocate struct zswap_entry for those pages
> completely.
> 
> There is also a very small performance improvement observed over 50 runs
> of kernel build test (kernbench) comparing the mean build time on a
> skylake machine when building the kernel in a cgroup v1 container with a
> 3G limit:
> 
> 		base		patched		% diff
> real		70.167		69.915		-0.359%
> user		2953.068	2956.147	+0.104%
> sys		2612.811	2594.718	-0.692%
> 
> This probably comes from more optimized operations like memchr_inv() and
> clear_highpage(). Note that the percentage of zero-filled pages during
> this test was only around 1.5% on average, and was not affected by this
> patch. Practical workloads could have a larger proportion of such pages
> (e.g. Johannes observed around 10% [1]), so the performance improvement
> should be larger.
> 
> [1]https://lore.kernel.org/linux-mm/[e-mail]/
> 
> Signed-off-by: Yosry Ahmed <[e-mail]>

This is an interesting direction to pursue, but I actually thinkg it
doesn't go far enough. Either way, I think it needs more data.

1) How frequent are non-zero-same-filled pages? Difficult to
   generalize, but if you could gather some from your fleet, that
   would be useful. If you can devise a portable strategy, I'd also be
   more than happy to gather this on ours (although I think you have
   more widespread zswap use, whereas we have more disk swap.)

2) The fact that we're doing any of this pattern analysis in zswap at
   all strikes me as a bit misguided. Being efficient about repetitive
   patterns is squarely in the domain of a compression algorithm. Do
   we not trust e.g. zstd to handle this properly?

   I'm guessing this goes back to inefficient packing from something
   like zbud, which would waste half a page on one repeating byte.

   But zsmalloc can do 32 byte objects. It's also a batching slab
   allocator, where storing a series of small, same-sized objects is
   quite fast.

   Add to that the additional branches, the additional kmap, the extra
   scanning of every single page for patterns - all in the fast path
   of zswap, when we already know that the vast majority of incoming
   pages will need to be properly compressed anyway.

   Maybe it's time to get rid of the special handling entirely?

Yosry Ahmed March 28, 2024, 8:23 p.m. UTC | #5

On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
>
> On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > The current same-filled pages handling supports pages filled with any
> > repeated word-sized pattern. However, in practice, most of these should
> > be zero pages anyway. Other patterns should be nearly as common.
> >
> > Drop the support for non-zero same-filled pages, but keep the names of
> > knobs exposed to userspace as "same_filled", which isn't entirely
> > inaccurate.
> >
> > This yields some nice code simplification and enables a following patch
> > that eliminates the need to allocate struct zswap_entry for those pages
> > completely.
> >
> > There is also a very small performance improvement observed over 50 runs
> > of kernel build test (kernbench) comparing the mean build time on a
> > skylake machine when building the kernel in a cgroup v1 container with a
> > 3G limit:
> >
> >               base            patched         % diff
> > real          70.167          69.915          -0.359%
> > user          2953.068        2956.147        +0.104%
> > sys           2612.811        2594.718        -0.692%
> >
> > This probably comes from more optimized operations like memchr_inv() and
> > clear_highpage(). Note that the percentage of zero-filled pages during
> > this test was only around 1.5% on average, and was not affected by this
> > patch. Practical workloads could have a larger proportion of such pages
> > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > should be larger.
> >
> > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> >
> > Signed-off-by: Yosry Ahmed <[e-mail]>
>
> This is an interesting direction to pursue, but I actually thinkg it
> doesn't go far enough. Either way, I think it needs more data.
>
> 1) How frequent are non-zero-same-filled pages? Difficult to
>    generalize, but if you could gather some from your fleet, that
>    would be useful. If you can devise a portable strategy, I'd also be
>    more than happy to gather this on ours (although I think you have
>    more widespread zswap use, whereas we have more disk swap.)

I am trying to collect the data, but there are.. hurdles. It would
take some time, so I was hoping the data could be collected elsewhere
if possible.

The idea I had was to hook a BPF program to the entry of
zswap_fill_page() and create a histogram of the "value" argument. We
would get more coverage by hooking it to the return of
zswap_is_page_same_filled() and only updating the histogram if the
return value is true, as it includes pages in zswap that haven't been
swapped in.

However, with zswap_is_page_same_filled() the BPF program will run in
all zswap stores, whereas for zswap_fill_page() it will only run when
needed. Not sure if this makes a practical difference tbh.

>
> 2) The fact that we're doing any of this pattern analysis in zswap at
>    all strikes me as a bit misguided. Being efficient about repetitive
>    patterns is squarely in the domain of a compression algorithm. Do
>    we not trust e.g. zstd to handle this properly?

I thought about this briefly, but I didn't follow through. I could try
to collect some data by swapping out different patterns and observing
how different compression algorithms react. That would be interesting
for sure.

>
>    I'm guessing this goes back to inefficient packing from something
>    like zbud, which would waste half a page on one repeating byte.
>
>    But zsmalloc can do 32 byte objects. It's also a batching slab
>    allocator, where storing a series of small, same-sized objects is
>    quite fast.
>
>    Add to that the additional branches, the additional kmap, the extra
>    scanning of every single page for patterns - all in the fast path
>    of zswap, when we already know that the vast majority of incoming
>    pages will need to be properly compressed anyway.
>
>    Maybe it's time to get rid of the special handling entirely?

We would still be wasting some memory (~96 bytes between zswap_entry
and zsmalloc object), and wasting cycling allocating them. This could
be made up for by cycles saved by removing the handling. We will be
saving some branches for sure. I am not worried about kmap as I think
it's a noop in most cases.

I am interested to see how much we could save by removing scanning for
patterns. We may not save much if we abort after reading a few words
in most cases, but I guess we could also be scanning a considerable
amount before aborting. On the other hand, we would be reading the
page contents into cache anyway for compression, so maybe it doesn't
really matter?

I will try to collect some data about this. I will start by trying to
find out how the compression algorithms handle same-filled pages. If
they can compress it efficiently, then I will try to get more data on
the tradeoff from removing the handling.

Thanks for the insights.

Johannes Weiner March 28, 2024, 9:07 p.m. UTC | #6

On Thu, Mar 28, 2024 at 01:23:42PM -0700, Yosry Ahmed wrote:
> On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> >
> > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > The current same-filled pages handling supports pages filled with any
> > > repeated word-sized pattern. However, in practice, most of these should
> > > be zero pages anyway. Other patterns should be nearly as common.
> > >
> > > Drop the support for non-zero same-filled pages, but keep the names of
> > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > inaccurate.
> > >
> > > This yields some nice code simplification and enables a following patch
> > > that eliminates the need to allocate struct zswap_entry for those pages
> > > completely.
> > >
> > > There is also a very small performance improvement observed over 50 runs
> > > of kernel build test (kernbench) comparing the mean build time on a
> > > skylake machine when building the kernel in a cgroup v1 container with a
> > > 3G limit:
> > >
> > >               base            patched         % diff
> > > real          70.167          69.915          -0.359%
> > > user          2953.068        2956.147        +0.104%
> > > sys           2612.811        2594.718        -0.692%
> > >
> > > This probably comes from more optimized operations like memchr_inv() and
> > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > this test was only around 1.5% on average, and was not affected by this
> > > patch. Practical workloads could have a larger proportion of such pages
> > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > should be larger.
> > >
> > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > >
> > > Signed-off-by: Yosry Ahmed <[e-mail]>
> >
> > This is an interesting direction to pursue, but I actually thinkg it
> > doesn't go far enough. Either way, I think it needs more data.
> >
> > 1) How frequent are non-zero-same-filled pages? Difficult to
> >    generalize, but if you could gather some from your fleet, that
> >    would be useful. If you can devise a portable strategy, I'd also be
> >    more than happy to gather this on ours (although I think you have
> >    more widespread zswap use, whereas we have more disk swap.)
> 
> I am trying to collect the data, but there are.. hurdles. It would
> take some time, so I was hoping the data could be collected elsewhere
> if possible.
> 
> The idea I had was to hook a BPF program to the entry of
> zswap_fill_page() and create a histogram of the "value" argument. We
> would get more coverage by hooking it to the return of
> zswap_is_page_same_filled() and only updating the histogram if the
> return value is true, as it includes pages in zswap that haven't been
> swapped in.
> 
> However, with zswap_is_page_same_filled() the BPF program will run in
> all zswap stores, whereas for zswap_fill_page() it will only run when
> needed. Not sure if this makes a practical difference tbh.
> 
> >
> > 2) The fact that we're doing any of this pattern analysis in zswap at
> >    all strikes me as a bit misguided. Being efficient about repetitive
> >    patterns is squarely in the domain of a compression algorithm. Do
> >    we not trust e.g. zstd to handle this properly?
> 
> I thought about this briefly, but I didn't follow through. I could try
> to collect some data by swapping out different patterns and observing
> how different compression algorithms react. That would be interesting
> for sure.
> 
> >
> >    I'm guessing this goes back to inefficient packing from something
> >    like zbud, which would waste half a page on one repeating byte.
> >
> >    But zsmalloc can do 32 byte objects. It's also a batching slab
> >    allocator, where storing a series of small, same-sized objects is
> >    quite fast.
> >
> >    Add to that the additional branches, the additional kmap, the extra
> >    scanning of every single page for patterns - all in the fast path
> >    of zswap, when we already know that the vast majority of incoming
> >    pages will need to be properly compressed anyway.
> >
> >    Maybe it's time to get rid of the special handling entirely?
> 
> We would still be wasting some memory (~96 bytes between zswap_entry
> and zsmalloc object), and wasting cycling allocating them. This could
> be made up for by cycles saved by removing the handling. We will be
> saving some branches for sure. I am not worried about kmap as I think
> it's a noop in most cases.

Yes, true.

> I am interested to see how much we could save by removing scanning for
> patterns. We may not save much if we abort after reading a few words
> in most cases, but I guess we could also be scanning a considerable
> amount before aborting. On the other hand, we would be reading the
> page contents into cache anyway for compression, so maybe it doesn't
> really matter?
> 
> I will try to collect some data about this. I will start by trying to
> find out how the compression algorithms handle same-filled pages. If
> they can compress it efficiently, then I will try to get more data on
> the tradeoff from removing the handling.

I do wonder if this could be overthinking it, too.

Double checking the numbers on our fleet, a 96 additional bytes for
each same-filled entry would result in a

1) p50 waste of 0.008% of total memory, and a

2) p99 waste of 0.06% of total memory.

And this is without us having even thought about trying to make
zsmalloc more efficient for this particular usecase - which might be
the better point of attack, if we think it's actually worth it.

So my take is that unless removing it would be outright horrible from
a %sys POV (which seems pretty unlikely), IMO it would be fine to just
delete it entirely with a "not worth the maintenance cost" argument.

If you turn the argument around, and somebody would submit the code as
it is today, with the numbers being what they are above, I'm not sure
we would even accept it!

E.g.

 mm/zswap.c | 114 ++++++-----------------------------------------------------
 1 file changed, 10 insertions(+), 104 deletions(-)

diff --git a/mm/zswap.c b/mm/zswap.c
index 741957f36f38..fc447f8a5c24 100644
--- a/mm/zswap.c
+++ b/mm/zswap.c
@@ -44,8 +44,6 @@
 **********************************/
 /* The number of compressed pages currently stored in zswap */
 atomic_t zswap_stored_pages = ATOMIC_INIT(0);
-/* The number of same-value filled pages currently stored in zswap */
-static atomic_t zswap_same_filled_pages = ATOMIC_INIT(0);
 
 /*
  * The statistics below are not protected from concurrent access for
@@ -123,19 +121,6 @@ static unsigned int zswap_accept_thr_percent = 90; /* of max pool size */
 module_param_named(accept_threshold_percent, zswap_accept_thr_percent,
 		   uint, 0644);
 
-/*
- * Enable/disable handling same-value filled pages (enabled by default).
- * If disabled every page is considered non-same-value filled.
- */
-static bool zswap_same_filled_pages_enabled = true;
-module_param_named(same_filled_pages_enabled, zswap_same_filled_pages_enabled,
-		   bool, 0644);
-
-/* Enable/disable handling non-same-value filled pages (enabled by default) */
-static bool zswap_non_same_filled_pages_enabled = true;
-module_param_named(non_same_filled_pages_enabled, zswap_non_same_filled_pages_enabled,
-		   bool, 0644);
-
 /* Number of zpools in zswap_pool (empirically determined for scalability) */
 #define ZSWAP_NR_ZPOOLS 32
 
@@ -194,12 +179,9 @@ static struct shrinker *zswap_shrinker;
  * page within zswap.
  *
  * swpentry - associated swap entry, the offset indexes into the red-black tree
- * length - the length in bytes of the compressed page data.  Needed during
- *          decompression. For a same value filled page length is 0, and both
- *          pool and lru are invalid and must be ignored.
+ * length - the length in bytes of the compressed page data
  * pool - the zswap_pool the entry's data is in
  * handle - zpool allocation handle that stores the compressed page data
- * value - value of the same-value filled pages which have same content
  * objcg - the obj_cgroup that the compressed memory is charged to
  * lru - handle to the pool's lru used to evict pages.
  */
@@ -207,10 +189,7 @@ struct zswap_entry {
 	swp_entry_t swpentry;
 	unsigned int length;
 	struct zswap_pool *pool;
-	union {
-		unsigned long handle;
-		unsigned long value;
-	};
+	unsigned long handle;
 	struct obj_cgroup *objcg;
 	struct list_head lru;
 };
@@ -812,13 +791,9 @@ static struct zpool *zswap_find_zpool(struct zswap_entry *entry)
  */
 static void zswap_entry_free(struct zswap_entry *entry)
 {
-	if (!entry->length)
-		atomic_dec(&zswap_same_filled_pages);
-	else {
-		zswap_lru_del(&zswap_list_lru, entry);
-		zpool_free(zswap_find_zpool(entry), entry->handle);
-		zswap_pool_put(entry->pool);
-	}
+	zswap_lru_del(&zswap_list_lru, entry);
+	zpool_free(zswap_find_zpool(entry), entry->handle);
+	zswap_pool_put(entry->pool);
 	if (entry->objcg) {
 		obj_cgroup_uncharge_zswap(entry->objcg, entry->length);
 		obj_cgroup_put(entry->objcg);
@@ -1253,11 +1228,6 @@ static unsigned long zswap_shrinker_count(struct shrinker *shrinker,
 	 * This ensures that the better zswap compresses memory, the fewer
 	 * pages we will evict to swap (as it will otherwise incur IO for
 	 * relatively small memory saving).
-	 *
-	 * The memory saving factor calculated here takes same-filled pages into
-	 * account, but those are not freeable since they almost occupy no
-	 * space. Hence, we may scale nr_freeable down a little bit more than we
-	 * should if we have a lot of same-filled pages.
 	 */
 	return mult_frac(nr_freeable, nr_backing, nr_stored);
 }
@@ -1361,36 +1331,6 @@ static void shrink_worker(struct work_struct *w)
 	} while (zswap_total_pages() > thr);
 }
 
-static int zswap_is_page_same_filled(void *ptr, unsigned long *value)
-{
-	unsigned long *page;
-	unsigned long val;
-	unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1;
-
-	page = (unsigned long *)ptr;
-	val = page[0];
-
-	if (val != page[last_pos])
-		return 0;
-
-	for (pos = 1; pos < last_pos; pos++) {
-		if (val != page[pos])
-			return 0;
-	}
-
-	*value = val;
-
-	return 1;
-}
-
-static void zswap_fill_page(void *ptr, unsigned long value)
-{
-	unsigned long *page;
-
-	page = (unsigned long *)ptr;
-	memset_l(page, value, PAGE_SIZE / sizeof(unsigned long));
-}
-
 bool zswap_store(struct folio *folio)
 {
 	swp_entry_t swp = folio->swap;
@@ -1446,24 +1386,6 @@ bool zswap_store(struct folio *folio)
 		goto reject;
 	}
 
-	if (zswap_same_filled_pages_enabled) {
-		unsigned long value;
-		u8 *src;
-
-		src = kmap_local_folio(folio, 0);
-		if (zswap_is_page_same_filled(src, &value)) {
-			kunmap_local(src);
-			entry->length = 0;
-			entry->value = value;
-			atomic_inc(&zswap_same_filled_pages);
-			goto insert_entry;
-		}
-		kunmap_local(src);
-	}
-
-	if (!zswap_non_same_filled_pages_enabled)
-		goto freepage;
-
 	/* if entry is successfully added, it keeps the reference */
 	entry->pool = zswap_pool_current_get();
 	if (!entry->pool)
@@ -1481,7 +1403,6 @@ bool zswap_store(struct folio *folio)
 	if (!zswap_compress(folio, entry))
 		goto put_pool;
 
-insert_entry:
 	entry->swpentry = swp;
 	entry->objcg = objcg;
 
@@ -1517,10 +1438,8 @@ bool zswap_store(struct folio *folio)
 	 *    The publishing order matters to prevent writeback from seeing
 	 *    an incoherent entry.
 	 */
-	if (entry->length) {
-		INIT_LIST_HEAD(&entry->lru);
-		zswap_lru_add(&zswap_list_lru, entry);
-	}
+	INIT_LIST_HEAD(&entry->lru);
+	zswap_lru_add(&zswap_list_lru, entry);
 
 	/* update stats */
 	atomic_inc(&zswap_stored_pages);
@@ -1529,13 +1448,9 @@ bool zswap_store(struct folio *folio)
 	return true;
 
 store_failed:
-	if (!entry->length)
-		atomic_dec(&zswap_same_filled_pages);
-	else {
-		zpool_free(zswap_find_zpool(entry), entry->handle);
+	zpool_free(zswap_find_zpool(entry), entry->handle);
 put_pool:
-		zswap_pool_put(entry->pool);
-	}
+	zswap_pool_put(entry->pool);
 freepage:
 	zswap_entry_cache_free(entry);
 reject:
@@ -1564,7 +1479,6 @@ bool zswap_load(struct folio *folio)
 	bool swapcache = folio_test_swapcache(folio);
 	struct xarray *tree = swap_zswap_tree(swp);
 	struct zswap_entry *entry;
-	u8 *dst;
 
 	VM_WARN_ON_ONCE(!folio_test_locked(folio));
 
@@ -1588,13 +1502,7 @@ bool zswap_load(struct folio *folio)
 	if (!entry)
 		return false;
 
-	if (entry->length)
-		zswap_decompress(entry, page);
-	else {
-		dst = kmap_local_page(page);
-		zswap_fill_page(dst, entry->value);
-		kunmap_local(dst);
-	}
+	zswap_decompress(entry, page);
 
 	count_vm_event(ZSWPIN);
 	if (entry->objcg)
@@ -1696,8 +1604,6 @@ static int zswap_debugfs_init(void)
 			    zswap_debugfs_root, NULL, &total_size_fops);
 	debugfs_create_atomic_t("stored_pages", 0444,
 				zswap_debugfs_root, &zswap_stored_pages);
-	debugfs_create_atomic_t("same_filled_pages", 0444,
-				zswap_debugfs_root, &zswap_same_filled_pages);
 
 	return 0;
 }

Nhat Pham March 28, 2024, 11:19 p.m. UTC | #7

On Thu, Mar 28, 2024 at 2:07 PM Johannes Weiner <[e-mail]> wrote:
>
> On Thu, Mar 28, 2024 at 01:23:42PM -0700, Yosry Ahmed wrote:
> > On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> > >
> > > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > > The current same-filled pages handling supports pages filled with any
> > > > repeated word-sized pattern. However, in practice, most of these should
> > > > be zero pages anyway. Other patterns should be nearly as common.
> > > >
> > > > Drop the support for non-zero same-filled pages, but keep the names of
> > > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > > inaccurate.
> > > >
> > > > This yields some nice code simplification and enables a following patch
> > > > that eliminates the need to allocate struct zswap_entry for those pages
> > > > completely.
> > > >
> > > > There is also a very small performance improvement observed over 50 runs
> > > > of kernel build test (kernbench) comparing the mean build time on a
> > > > skylake machine when building the kernel in a cgroup v1 container with a
> > > > 3G limit:
> > > >
> > > >               base            patched         % diff
> > > > real          70.167          69.915          -0.359%
> > > > user          2953.068        2956.147        +0.104%
> > > > sys           2612.811        2594.718        -0.692%
> > > >
> > > > This probably comes from more optimized operations like memchr_inv() and
> > > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > > this test was only around 1.5% on average, and was not affected by this
> > > > patch. Practical workloads could have a larger proportion of such pages
> > > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > > should be larger.
> > > >
> > > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > > >
> > > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > >
> > > This is an interesting direction to pursue, but I actually thinkg it
> > > doesn't go far enough. Either way, I think it needs more data.
> > >
> > > 1) How frequent are non-zero-same-filled pages? Difficult to
> > >    generalize, but if you could gather some from your fleet, that
> > >    would be useful. If you can devise a portable strategy, I'd also be
> > >    more than happy to gather this on ours (although I think you have
> > >    more widespread zswap use, whereas we have more disk swap.)
> >
> > I am trying to collect the data, but there are.. hurdles. It would
> > take some time, so I was hoping the data could be collected elsewhere
> > if possible.
> >
> > The idea I had was to hook a BPF program to the entry of
> > zswap_fill_page() and create a histogram of the "value" argument. We
> > would get more coverage by hooking it to the return of
> > zswap_is_page_same_filled() and only updating the histogram if the
> > return value is true, as it includes pages in zswap that haven't been
> > swapped in.
> >
> > However, with zswap_is_page_same_filled() the BPF program will run in
> > all zswap stores, whereas for zswap_fill_page() it will only run when
> > needed. Not sure if this makes a practical difference tbh.
> >
> > >
> > > 2) The fact that we're doing any of this pattern analysis in zswap at
> > >    all strikes me as a bit misguided. Being efficient about repetitive
> > >    patterns is squarely in the domain of a compression algorithm. Do
> > >    we not trust e.g. zstd to handle this properly?
> >
> > I thought about this briefly, but I didn't follow through. I could try
> > to collect some data by swapping out different patterns and observing
> > how different compression algorithms react. That would be interesting
> > for sure.
> >
> > >
> > >    I'm guessing this goes back to inefficient packing from something
> > >    like zbud, which would waste half a page on one repeating byte.
> > >
> > >    But zsmalloc can do 32 byte objects. It's also a batching slab
> > >    allocator, where storing a series of small, same-sized objects is
> > >    quite fast.
> > >
> > >    Add to that the additional branches, the additional kmap, the extra
> > >    scanning of every single page for patterns - all in the fast path
> > >    of zswap, when we already know that the vast majority of incoming
> > >    pages will need to be properly compressed anyway.
> > >
> > >    Maybe it's time to get rid of the special handling entirely?
> >
> > We would still be wasting some memory (~96 bytes between zswap_entry
> > and zsmalloc object), and wasting cycling allocating them. This could
> > be made up for by cycles saved by removing the handling. We will be
> > saving some branches for sure. I am not worried about kmap as I think
> > it's a noop in most cases.
>
> Yes, true.
>
> > I am interested to see how much we could save by removing scanning for
> > patterns. We may not save much if we abort after reading a few words
> > in most cases, but I guess we could also be scanning a considerable
> > amount before aborting. On the other hand, we would be reading the
> > page contents into cache anyway for compression, so maybe it doesn't
> > really matter?
> >
> > I will try to collect some data about this. I will start by trying to
> > find out how the compression algorithms handle same-filled pages. If
> > they can compress it efficiently, then I will try to get more data on
> > the tradeoff from removing the handling.
>
> I do wonder if this could be overthinking it, too.
>
> Double checking the numbers on our fleet, a 96 additional bytes for
> each same-filled entry would result in a
>
> 1) p50 waste of 0.008% of total memory, and a
>
> 2) p99 waste of 0.06% of total memory.
>
> And this is without us having even thought about trying to make
> zsmalloc more efficient for this particular usecase - which might be
> the better point of attack, if we think it's actually worth it.
>
> So my take is that unless removing it would be outright horrible from
> a %sys POV (which seems pretty unlikely), IMO it would be fine to just
> delete it entirely with a "not worth the maintenance cost" argument.
>
> If you turn the argument around, and somebody would submit the code as
> it is today, with the numbers being what they are above, I'm not sure
> we would even accept it!

The context guy is here :)

Not arguing for one way or another, but I did find the original patch
that introduced same filled page handling:

https://github.com/torvalds/linux/commit/a85f878b443f8d2b91ba76f09da21ac0af22e07f

https://lore.kernel.org/all/20171018104832epcms5p1b2232e2236258de3d03d1344dde9fce0@epcms5p1/T/#u

The number looks impressive, and there is some detail about the
experiment setup, but I can't seem to find what the allocator +
compressor used.

Which, as Johannes has pointed out, matters a lot. A good compressor
(which should work on arguably the most trivial data pattern there is)
+ a backend allocator that is capable of handling small objects well
could make this case really efficient, without resorting to special
handling at the zswap level.

Nhat Pham March 28, 2024, 11:33 p.m. UTC | #8

On Thu, Mar 28, 2024 at 1:24 PM Yosry Ahmed <[e-mail]> wrote:
>
> On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> >
> > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > The current same-filled pages handling supports pages filled with any
> > > repeated word-sized pattern. However, in practice, most of these should
> > > be zero pages anyway. Other patterns should be nearly as common.
> > >
> > > Drop the support for non-zero same-filled pages, but keep the names of
> > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > inaccurate.
> > >
> > > This yields some nice code simplification and enables a following patch
> > > that eliminates the need to allocate struct zswap_entry for those pages
> > > completely.
> > >
> > > There is also a very small performance improvement observed over 50 runs
> > > of kernel build test (kernbench) comparing the mean build time on a
> > > skylake machine when building the kernel in a cgroup v1 container with a
> > > 3G limit:
> > >
> > >               base            patched         % diff
> > > real          70.167          69.915          -0.359%
> > > user          2953.068        2956.147        +0.104%
> > > sys           2612.811        2594.718        -0.692%
> > >
> > > This probably comes from more optimized operations like memchr_inv() and
> > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > this test was only around 1.5% on average, and was not affected by this
> > > patch. Practical workloads could have a larger proportion of such pages
> > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > should be larger.
> > >
> > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > >
> > > Signed-off-by: Yosry Ahmed <[e-mail]>
> >
> > This is an interesting direction to pursue, but I actually thinkg it
> > doesn't go far enough. Either way, I think it needs more data.
> >
> > 1) How frequent are non-zero-same-filled pages? Difficult to
> >    generalize, but if you could gather some from your fleet, that
> >    would be useful. If you can devise a portable strategy, I'd also be
> >    more than happy to gather this on ours (although I think you have
> >    more widespread zswap use, whereas we have more disk swap.)
>
> I am trying to collect the data, but there are.. hurdles. It would
> take some time, so I was hoping the data could be collected elsewhere
> if possible.
>
> The idea I had was to hook a BPF program to the entry of
> zswap_fill_page() and create a histogram of the "value" argument. We
> would get more coverage by hooking it to the return of
> zswap_is_page_same_filled() and only updating the histogram if the
> return value is true, as it includes pages in zswap that haven't been
> swapped in.
>
> However, with zswap_is_page_same_filled() the BPF program will run in
> all zswap stores, whereas for zswap_fill_page() it will only run when
> needed. Not sure if this makes a practical difference tbh.
>
> >
> > 2) The fact that we're doing any of this pattern analysis in zswap at
> >    all strikes me as a bit misguided. Being efficient about repetitive
> >    patterns is squarely in the domain of a compression algorithm. Do
> >    we not trust e.g. zstd to handle this properly?
>
> I thought about this briefly, but I didn't follow through. I could try
> to collect some data by swapping out different patterns and observing
> how different compression algorithms react. That would be interesting
> for sure.
>
> >
> >    I'm guessing this goes back to inefficient packing from something
> >    like zbud, which would waste half a page on one repeating byte.
> >
> >    But zsmalloc can do 32 byte objects. It's also a batching slab
> >    allocator, where storing a series of small, same-sized objects is
> >    quite fast.
> >
> >    Add to that the additional branches, the additional kmap, the extra
> >    scanning of every single page for patterns - all in the fast path
> >    of zswap, when we already know that the vast majority of incoming
> >    pages will need to be properly compressed anyway.
> >
> >    Maybe it's time to get rid of the special handling entirely?
>
> We would still be wasting some memory (~96 bytes between zswap_entry
> and zsmalloc object), and wasting cycling allocating them. This could
> be made up for by cycles saved by removing the handling. We will be
> saving some branches for sure. I am not worried about kmap as I think
> it's a noop in most cases.

A secondary effect of the current same-filled page handling is that
we're not considering them for reclaim. Which could potentially be
beneficial, because we're not saving much memory (essentially just the
zswap entry and associated cost of storing them) by writing these
pages back - IOW, the cost / benefit ratio for reclaiming these pages
is quite atrocious.

Again, all of this is just handwaving without numbers. It'd be nice if
we can have more concrete data for this conversation :P

Yosry Ahmed March 29, 2024, 2:05 a.m. UTC | #9

On Thu, Mar 28, 2024 at 4:19 PM Nhat Pham <[e-mail]> wrote:
>
> On Thu, Mar 28, 2024 at 2:07 PM Johannes Weiner <[e-mail]> wrote:
> >
> > On Thu, Mar 28, 2024 at 01:23:42PM -0700, Yosry Ahmed wrote:
> > > On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> > > >
> > > > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > > > The current same-filled pages handling supports pages filled with any
> > > > > repeated word-sized pattern. However, in practice, most of these should
> > > > > be zero pages anyway. Other patterns should be nearly as common.
> > > > >
> > > > > Drop the support for non-zero same-filled pages, but keep the names of
> > > > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > > > inaccurate.
> > > > >
> > > > > This yields some nice code simplification and enables a following patch
> > > > > that eliminates the need to allocate struct zswap_entry for those pages
> > > > > completely.
> > > > >
> > > > > There is also a very small performance improvement observed over 50 runs
> > > > > of kernel build test (kernbench) comparing the mean build time on a
> > > > > skylake machine when building the kernel in a cgroup v1 container with a
> > > > > 3G limit:
> > > > >
> > > > >               base            patched         % diff
> > > > > real          70.167          69.915          -0.359%
> > > > > user          2953.068        2956.147        +0.104%
> > > > > sys           2612.811        2594.718        -0.692%
> > > > >
> > > > > This probably comes from more optimized operations like memchr_inv() and
> > > > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > > > this test was only around 1.5% on average, and was not affected by this
> > > > > patch. Practical workloads could have a larger proportion of such pages
> > > > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > > > should be larger.
> > > > >
> > > > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > > > >
> > > > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > > >
> > > > This is an interesting direction to pursue, but I actually thinkg it
> > > > doesn't go far enough. Either way, I think it needs more data.
> > > >
> > > > 1) How frequent are non-zero-same-filled pages? Difficult to
> > > >    generalize, but if you could gather some from your fleet, that
> > > >    would be useful. If you can devise a portable strategy, I'd also be
> > > >    more than happy to gather this on ours (although I think you have
> > > >    more widespread zswap use, whereas we have more disk swap.)
> > >
> > > I am trying to collect the data, but there are.. hurdles. It would
> > > take some time, so I was hoping the data could be collected elsewhere
> > > if possible.
> > >
> > > The idea I had was to hook a BPF program to the entry of
> > > zswap_fill_page() and create a histogram of the "value" argument. We
> > > would get more coverage by hooking it to the return of
> > > zswap_is_page_same_filled() and only updating the histogram if the
> > > return value is true, as it includes pages in zswap that haven't been
> > > swapped in.
> > >
> > > However, with zswap_is_page_same_filled() the BPF program will run in
> > > all zswap stores, whereas for zswap_fill_page() it will only run when
> > > needed. Not sure if this makes a practical difference tbh.
> > >
> > > >
> > > > 2) The fact that we're doing any of this pattern analysis in zswap at
> > > >    all strikes me as a bit misguided. Being efficient about repetitive
> > > >    patterns is squarely in the domain of a compression algorithm. Do
> > > >    we not trust e.g. zstd to handle this properly?
> > >
> > > I thought about this briefly, but I didn't follow through. I could try
> > > to collect some data by swapping out different patterns and observing
> > > how different compression algorithms react. That would be interesting
> > > for sure.
> > >
> > > >
> > > >    I'm guessing this goes back to inefficient packing from something
> > > >    like zbud, which would waste half a page on one repeating byte.
> > > >
> > > >    But zsmalloc can do 32 byte objects. It's also a batching slab
> > > >    allocator, where storing a series of small, same-sized objects is
> > > >    quite fast.
> > > >
> > > >    Add to that the additional branches, the additional kmap, the extra
> > > >    scanning of every single page for patterns - all in the fast path
> > > >    of zswap, when we already know that the vast majority of incoming
> > > >    pages will need to be properly compressed anyway.
> > > >
> > > >    Maybe it's time to get rid of the special handling entirely?
> > >
> > > We would still be wasting some memory (~96 bytes between zswap_entry
> > > and zsmalloc object), and wasting cycling allocating them. This could
> > > be made up for by cycles saved by removing the handling. We will be
> > > saving some branches for sure. I am not worried about kmap as I think
> > > it's a noop in most cases.
> >
> > Yes, true.
> >
> > > I am interested to see how much we could save by removing scanning for
> > > patterns. We may not save much if we abort after reading a few words
> > > in most cases, but I guess we could also be scanning a considerable
> > > amount before aborting. On the other hand, we would be reading the
> > > page contents into cache anyway for compression, so maybe it doesn't
> > > really matter?
> > >
> > > I will try to collect some data about this. I will start by trying to
> > > find out how the compression algorithms handle same-filled pages. If
> > > they can compress it efficiently, then I will try to get more data on
> > > the tradeoff from removing the handling.
> >
> > I do wonder if this could be overthinking it, too.
> >
> > Double checking the numbers on our fleet, a 96 additional bytes for
> > each same-filled entry would result in a
> >
> > 1) p50 waste of 0.008% of total memory, and a
> >
> > 2) p99 waste of 0.06% of total memory.

Right. Assuming the compressors do not surprise us and store
same-filled pages in an absurd way, it's not worth it in terms of
memory savings.

> >
> > And this is without us having even thought about trying to make
> > zsmalloc more efficient for this particular usecase - which might be
> > the better point of attack, if we think it's actually worth it.
> >
> > So my take is that unless removing it would be outright horrible from
> > a %sys POV (which seems pretty unlikely), IMO it would be fine to just
> > delete it entirely with a "not worth the maintenance cost" argument.
> >
> > If you turn the argument around, and somebody would submit the code as
> > it is today, with the numbers being what they are above, I'm not sure
> > we would even accept it!
>
> The context guy is here :)
>
> Not arguing for one way or another, but I did find the original patch
> that introduced same filled page handling:
>
> https://github.com/torvalds/linux/commit/a85f878b443f8d2b91ba76f09da21ac0af22e07f
>
> https://lore.kernel.org/all/20171018104832epcms5p1b2232e2236258de3d03d1344dde9fce0@epcms5p1/T/#u

Thanks for digging this up. I don't know why I didn't start there :)

Following in your footsteps, and given that zram has the same feature,
I found the patch that added support for non-zero same-filled pages in
zram:
https://lore.kernel.org/all/[e-mail]/#t

Both of them confirm that most same-filled pages are zero pages, but
they show a more significant portion of same-filled pages being
non-zero (17% to 40%). I suspect this will be less in data centers
compared to consumer apps.

The zswap patch also reports significant performance improvements from
the same-filled handling, but this is with 17-22% same-filled pages.
Johannes mentioned around 10% in your data centers, so the performance
improvement would be less. In the kernel build tests I ran with only
around 1.5% same-filled pages I observed 1.4% improvements just by
optimizing them (only zero-filled, skipping allocations).

So I think removing the same-filled pages handling completely may be
too aggressive, because it doesn't only affect the memory efficiency,
but also cycles spent when handling those pages. Just avoiding going
through the allocator and compressor has to account for something :)

>
> The number looks impressive, and there is some detail about the
> experiment setup, but I can't seem to find what the allocator +
> compressor used.

I would assume it was zbud because it was the default then, but as I
mentioned zram had similar patches and it uses zsmalloc. I suspect
zsmalloc would have changed since then tho, and compressors as well.
With zram there, is also the point that metadata is allocated
statically AFAICT, so there is very little cost to supporting all
same-filled pages if you already support zero-filled pages.

>
> Which, as Johannes has pointed out, matters a lot. A good compressor
> (which should work on arguably the most trivial data pattern there is)
> + a backend allocator that is capable of handling small objects well
> could make this case really efficient, without resorting to special
> handling at the zswap level.

All in all, I think there are three aspects here:
(1) Cycles saved by avoiding going through the compressor and
allocator, and potentially allocating zswap_entry as well the metadata
with this series.

(2) Memory saved by storing same-filled pages in zswap instead of
compressing them. This will ultimately depend on the compressor and
allocator as has been established.

(3) Memory saved on metadata in zswap by avoiding the zswap_entry
allocation. This is probably too small to matter.

I think (1) may be the major factor here, and (2) could be a factor if
the compressors surprise us (and would always be a factor for zbud and
z3fold due to bin packing).

Focusing on just (1), supporting zero-filled pages only may be a good
tradeoff. We get slightly less complicated and potentially faster
handling in zswap without losing a lot. Did I capture the discussion
so far correctly?

Yosry Ahmed March 29, 2024, 2:07 a.m. UTC | #10

On Thu, Mar 28, 2024 at 4:34 PM Nhat Pham <[e-mail]> wrote:
>
> On Thu, Mar 28, 2024 at 1:24 PM Yosry Ahmed <[e-mail]> wrote:
> >
> > On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> > >
> > > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > > The current same-filled pages handling supports pages filled with any
> > > > repeated word-sized pattern. However, in practice, most of these should
> > > > be zero pages anyway. Other patterns should be nearly as common.
> > > >
> > > > Drop the support for non-zero same-filled pages, but keep the names of
> > > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > > inaccurate.
> > > >
> > > > This yields some nice code simplification and enables a following patch
> > > > that eliminates the need to allocate struct zswap_entry for those pages
> > > > completely.
> > > >
> > > > There is also a very small performance improvement observed over 50 runs
> > > > of kernel build test (kernbench) comparing the mean build time on a
> > > > skylake machine when building the kernel in a cgroup v1 container with a
> > > > 3G limit:
> > > >
> > > >               base            patched         % diff
> > > > real          70.167          69.915          -0.359%
> > > > user          2953.068        2956.147        +0.104%
> > > > sys           2612.811        2594.718        -0.692%
> > > >
> > > > This probably comes from more optimized operations like memchr_inv() and
> > > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > > this test was only around 1.5% on average, and was not affected by this
> > > > patch. Practical workloads could have a larger proportion of such pages
> > > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > > should be larger.
> > > >
> > > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > > >
> > > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > >
> > > This is an interesting direction to pursue, but I actually thinkg it
> > > doesn't go far enough. Either way, I think it needs more data.
> > >
> > > 1) How frequent are non-zero-same-filled pages? Difficult to
> > >    generalize, but if you could gather some from your fleet, that
> > >    would be useful. If you can devise a portable strategy, I'd also be
> > >    more than happy to gather this on ours (although I think you have
> > >    more widespread zswap use, whereas we have more disk swap.)
> >
> > I am trying to collect the data, but there are.. hurdles. It would
> > take some time, so I was hoping the data could be collected elsewhere
> > if possible.
> >
> > The idea I had was to hook a BPF program to the entry of
> > zswap_fill_page() and create a histogram of the "value" argument. We
> > would get more coverage by hooking it to the return of
> > zswap_is_page_same_filled() and only updating the histogram if the
> > return value is true, as it includes pages in zswap that haven't been
> > swapped in.
> >
> > However, with zswap_is_page_same_filled() the BPF program will run in
> > all zswap stores, whereas for zswap_fill_page() it will only run when
> > needed. Not sure if this makes a practical difference tbh.
> >
> > >
> > > 2) The fact that we're doing any of this pattern analysis in zswap at
> > >    all strikes me as a bit misguided. Being efficient about repetitive
> > >    patterns is squarely in the domain of a compression algorithm. Do
> > >    we not trust e.g. zstd to handle this properly?
> >
> > I thought about this briefly, but I didn't follow through. I could try
> > to collect some data by swapping out different patterns and observing
> > how different compression algorithms react. That would be interesting
> > for sure.
> >
> > >
> > >    I'm guessing this goes back to inefficient packing from something
> > >    like zbud, which would waste half a page on one repeating byte.
> > >
> > >    But zsmalloc can do 32 byte objects. It's also a batching slab
> > >    allocator, where storing a series of small, same-sized objects is
> > >    quite fast.
> > >
> > >    Add to that the additional branches, the additional kmap, the extra
> > >    scanning of every single page for patterns - all in the fast path
> > >    of zswap, when we already know that the vast majority of incoming
> > >    pages will need to be properly compressed anyway.
> > >
> > >    Maybe it's time to get rid of the special handling entirely?
> >
> > We would still be wasting some memory (~96 bytes between zswap_entry
> > and zsmalloc object), and wasting cycling allocating them. This could
> > be made up for by cycles saved by removing the handling. We will be
> > saving some branches for sure. I am not worried about kmap as I think
> > it's a noop in most cases.
>
> A secondary effect of the current same-filled page handling is that
> we're not considering them for reclaim. Which could potentially be
> beneficial, because we're not saving much memory (essentially just the
> zswap entry and associated cost of storing them) by writing these
> pages back - IOW, the cost / benefit ratio for reclaiming these pages
> is quite atrocious.

Yes, but I think this applies even without same-filled pages. Johannes
mentioned that zsmalloc could store compressed pages down to 32 bytes
in size. If these are common, it would be absurd to them out too. We
already have some kind of heuristic in the shrinker to slowdown
writeback if the compression ratio is high. Perhaps it's worth
skipping writeback completely for some pages on the LRU, even if this
means we violate the LRU ordering. We already do this for same-filled
pages, so it may make sense to generalize it.

>
> Again, all of this is just handwaving without numbers. It'd be nice if
> we can have more concrete data for this conversation :P

Yosry Ahmed March 29, 2024, 4:27 a.m. UTC | #11

On Thu, Mar 28, 2024 at 7:05 PM Yosry Ahmed <[e-mail]> wrote:
>
> On Thu, Mar 28, 2024 at 4:19 PM Nhat Pham <[e-mail]> wrote:
> >
> > On Thu, Mar 28, 2024 at 2:07 PM Johannes Weiner <[e-mail]> wrote:
> > >
> > > On Thu, Mar 28, 2024 at 01:23:42PM -0700, Yosry Ahmed wrote:
> > > > On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> > > > >
> > > > > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > > > > The current same-filled pages handling supports pages filled with any
> > > > > > repeated word-sized pattern. However, in practice, most of these should
> > > > > > be zero pages anyway. Other patterns should be nearly as common.
> > > > > >
> > > > > > Drop the support for non-zero same-filled pages, but keep the names of
> > > > > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > > > > inaccurate.
> > > > > >
> > > > > > This yields some nice code simplification and enables a following patch
> > > > > > that eliminates the need to allocate struct zswap_entry for those pages
> > > > > > completely.
> > > > > >
> > > > > > There is also a very small performance improvement observed over 50 runs
> > > > > > of kernel build test (kernbench) comparing the mean build time on a
> > > > > > skylake machine when building the kernel in a cgroup v1 container with a
> > > > > > 3G limit:
> > > > > >
> > > > > >               base            patched         % diff
> > > > > > real          70.167          69.915          -0.359%
> > > > > > user          2953.068        2956.147        +0.104%
> > > > > > sys           2612.811        2594.718        -0.692%
> > > > > >
> > > > > > This probably comes from more optimized operations like memchr_inv() and
> > > > > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > > > > this test was only around 1.5% on average, and was not affected by this
> > > > > > patch. Practical workloads could have a larger proportion of such pages
> > > > > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > > > > should be larger.
> > > > > >
> > > > > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > > > > >
> > > > > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > > > >
> > > > > This is an interesting direction to pursue, but I actually thinkg it
> > > > > doesn't go far enough. Either way, I think it needs more data.
> > > > >
> > > > > 1) How frequent are non-zero-same-filled pages? Difficult to
> > > > >    generalize, but if you could gather some from your fleet, that
> > > > >    would be useful. If you can devise a portable strategy, I'd also be
> > > > >    more than happy to gather this on ours (although I think you have
> > > > >    more widespread zswap use, whereas we have more disk swap.)
> > > >
> > > > I am trying to collect the data, but there are.. hurdles. It would
> > > > take some time, so I was hoping the data could be collected elsewhere
> > > > if possible.
> > > >
> > > > The idea I had was to hook a BPF program to the entry of
> > > > zswap_fill_page() and create a histogram of the "value" argument. We
> > > > would get more coverage by hooking it to the return of
> > > > zswap_is_page_same_filled() and only updating the histogram if the
> > > > return value is true, as it includes pages in zswap that haven't been
> > > > swapped in.
> > > >
> > > > However, with zswap_is_page_same_filled() the BPF program will run in
> > > > all zswap stores, whereas for zswap_fill_page() it will only run when
> > > > needed. Not sure if this makes a practical difference tbh.
> > > >
> > > > >
> > > > > 2) The fact that we're doing any of this pattern analysis in zswap at
> > > > >    all strikes me as a bit misguided. Being efficient about repetitive
> > > > >    patterns is squarely in the domain of a compression algorithm. Do
> > > > >    we not trust e.g. zstd to handle this properly?
> > > >
> > > > I thought about this briefly, but I didn't follow through. I could try
> > > > to collect some data by swapping out different patterns and observing
> > > > how different compression algorithms react. That would be interesting
> > > > for sure.
> > > >
> > > > >
> > > > >    I'm guessing this goes back to inefficient packing from something
> > > > >    like zbud, which would waste half a page on one repeating byte.
> > > > >
> > > > >    But zsmalloc can do 32 byte objects. It's also a batching slab
> > > > >    allocator, where storing a series of small, same-sized objects is
> > > > >    quite fast.
> > > > >
> > > > >    Add to that the additional branches, the additional kmap, the extra
> > > > >    scanning of every single page for patterns - all in the fast path
> > > > >    of zswap, when we already know that the vast majority of incoming
> > > > >    pages will need to be properly compressed anyway.
> > > > >
> > > > >    Maybe it's time to get rid of the special handling entirely?
> > > >
> > > > We would still be wasting some memory (~96 bytes between zswap_entry
> > > > and zsmalloc object), and wasting cycling allocating them. This could
> > > > be made up for by cycles saved by removing the handling. We will be
> > > > saving some branches for sure. I am not worried about kmap as I think
> > > > it's a noop in most cases.
> > >
> > > Yes, true.
> > >
> > > > I am interested to see how much we could save by removing scanning for
> > > > patterns. We may not save much if we abort after reading a few words
> > > > in most cases, but I guess we could also be scanning a considerable
> > > > amount before aborting. On the other hand, we would be reading the
> > > > page contents into cache anyway for compression, so maybe it doesn't
> > > > really matter?
> > > >
> > > > I will try to collect some data about this. I will start by trying to
> > > > find out how the compression algorithms handle same-filled pages. If
> > > > they can compress it efficiently, then I will try to get more data on
> > > > the tradeoff from removing the handling.
> > >
> > > I do wonder if this could be overthinking it, too.
> > >
> > > Double checking the numbers on our fleet, a 96 additional bytes for
> > > each same-filled entry would result in a
> > >
> > > 1) p50 waste of 0.008% of total memory, and a
> > >
> > > 2) p99 waste of 0.06% of total memory.
>
> Right. Assuming the compressors do not surprise us and store
> same-filled pages in an absurd way, it's not worth it in terms of
> memory savings.
>
> > >
> > > And this is without us having even thought about trying to make
> > > zsmalloc more efficient for this particular usecase - which might be
> > > the better point of attack, if we think it's actually worth it.
> > >
> > > So my take is that unless removing it would be outright horrible from
> > > a %sys POV (which seems pretty unlikely), IMO it would be fine to just
> > > delete it entirely with a "not worth the maintenance cost" argument.
> > >
> > > If you turn the argument around, and somebody would submit the code as
> > > it is today, with the numbers being what they are above, I'm not sure
> > > we would even accept it!
> >
> > The context guy is here :)
> >
> > Not arguing for one way or another, but I did find the original patch
> > that introduced same filled page handling:
> >
> > https://github.com/torvalds/linux/commit/a85f878b443f8d2b91ba76f09da21ac0af22e07f
> >
> > https://lore.kernel.org/all/20171018104832epcms5p1b2232e2236258de3d03d1344dde9fce0@epcms5p1/T/#u
>
> Thanks for digging this up. I don't know why I didn't start there :)
>
> Following in your footsteps, and given that zram has the same feature,
> I found the patch that added support for non-zero same-filled pages in
> zram:
> https://lore.kernel.org/all/[e-mail]/#t
>
> Both of them confirm that most same-filled pages are zero pages, but
> they show a more significant portion of same-filled pages being
> non-zero (17% to 40%). I suspect this will be less in data centers
> compared to consumer apps.
>
> The zswap patch also reports significant performance improvements from
> the same-filled handling, but this is with 17-22% same-filled pages.
> Johannes mentioned around 10% in your data centers, so the performance
> improvement would be less. In the kernel build tests I ran with only
> around 1.5% same-filled pages I observed 1.4% improvements just by
> optimizing them (only zero-filled, skipping allocations).
>
> So I think removing the same-filled pages handling completely may be
> too aggressive, because it doesn't only affect the memory efficiency,
> but also cycles spent when handling those pages. Just avoiding going
> through the allocator and compressor has to account for something :)

Here is another data point. I tried removing the same-filled handling
code completely with the diff Johannes sent upthread. I saw 1.3%
improvement in the kernel build test, very similar to the improvement
from this patch series. _However_, the kernel build test only produces
~1.5% zero-filled pages in my runs. More realistic workloads have
significantly higher percentages as demonstrated upthread.

In other words, the kernel build test (at least in my runs) seems to
be the worst case scenario for same-filled/zero-filled pages. Since
the improvement from removing same-filled handling is quite small in
this case, I suspect there will be no improvement, but possibly a
regression, on real workloads.

As the zero-filled pages ratio increases:
- The performance with this series will improve.
- The performance with removing same-filled handling completely will
become worse.

Johannes Weiner March 29, 2024, 5:37 p.m. UTC | #12

On Thu, Mar 28, 2024 at 09:27:17PM -0700, Yosry Ahmed wrote:
> On Thu, Mar 28, 2024 at 7:05 PM Yosry Ahmed <[e-mail]> wrote:
> >
> > On Thu, Mar 28, 2024 at 4:19 PM Nhat Pham <[e-mail]> wrote:
> > >
> > > On Thu, Mar 28, 2024 at 2:07 PM Johannes Weiner <[e-mail]> wrote:
> > > >
> > > > On Thu, Mar 28, 2024 at 01:23:42PM -0700, Yosry Ahmed wrote:
> > > > > On Thu, Mar 28, 2024 at 12:31 PM Johannes Weiner <[e-mail]> wrote:
> > > > > >
> > > > > > On Mon, Mar 25, 2024 at 11:50:14PM +0000, Yosry Ahmed wrote:
> > > > > > > The current same-filled pages handling supports pages filled with any
> > > > > > > repeated word-sized pattern. However, in practice, most of these should
> > > > > > > be zero pages anyway. Other patterns should be nearly as common.
> > > > > > >
> > > > > > > Drop the support for non-zero same-filled pages, but keep the names of
> > > > > > > knobs exposed to userspace as "same_filled", which isn't entirely
> > > > > > > inaccurate.
> > > > > > >
> > > > > > > This yields some nice code simplification and enables a following patch
> > > > > > > that eliminates the need to allocate struct zswap_entry for those pages
> > > > > > > completely.
> > > > > > >
> > > > > > > There is also a very small performance improvement observed over 50 runs
> > > > > > > of kernel build test (kernbench) comparing the mean build time on a
> > > > > > > skylake machine when building the kernel in a cgroup v1 container with a
> > > > > > > 3G limit:
> > > > > > >
> > > > > > >               base            patched         % diff
> > > > > > > real          70.167          69.915          -0.359%
> > > > > > > user          2953.068        2956.147        +0.104%
> > > > > > > sys           2612.811        2594.718        -0.692%
> > > > > > >
> > > > > > > This probably comes from more optimized operations like memchr_inv() and
> > > > > > > clear_highpage(). Note that the percentage of zero-filled pages during
> > > > > > > this test was only around 1.5% on average, and was not affected by this
> > > > > > > patch. Practical workloads could have a larger proportion of such pages
> > > > > > > (e.g. Johannes observed around 10% [1]), so the performance improvement
> > > > > > > should be larger.
> > > > > > >
> > > > > > > [1]https://lore.kernel.org/linux-mm/[e-mail]/
> > > > > > >
> > > > > > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > > > > >
> > > > > > This is an interesting direction to pursue, but I actually thinkg it
> > > > > > doesn't go far enough. Either way, I think it needs more data.
> > > > > >
> > > > > > 1) How frequent are non-zero-same-filled pages? Difficult to
> > > > > >    generalize, but if you could gather some from your fleet, that
> > > > > >    would be useful. If you can devise a portable strategy, I'd also be
> > > > > >    more than happy to gather this on ours (although I think you have
> > > > > >    more widespread zswap use, whereas we have more disk swap.)
> > > > >
> > > > > I am trying to collect the data, but there are.. hurdles. It would
> > > > > take some time, so I was hoping the data could be collected elsewhere
> > > > > if possible.
> > > > >
> > > > > The idea I had was to hook a BPF program to the entry of
> > > > > zswap_fill_page() and create a histogram of the "value" argument. We
> > > > > would get more coverage by hooking it to the return of
> > > > > zswap_is_page_same_filled() and only updating the histogram if the
> > > > > return value is true, as it includes pages in zswap that haven't been
> > > > > swapped in.
> > > > >
> > > > > However, with zswap_is_page_same_filled() the BPF program will run in
> > > > > all zswap stores, whereas for zswap_fill_page() it will only run when
> > > > > needed. Not sure if this makes a practical difference tbh.
> > > > >
> > > > > >
> > > > > > 2) The fact that we're doing any of this pattern analysis in zswap at
> > > > > >    all strikes me as a bit misguided. Being efficient about repetitive
> > > > > >    patterns is squarely in the domain of a compression algorithm. Do
> > > > > >    we not trust e.g. zstd to handle this properly?
> > > > >
> > > > > I thought about this briefly, but I didn't follow through. I could try
> > > > > to collect some data by swapping out different patterns and observing
> > > > > how different compression algorithms react. That would be interesting
> > > > > for sure.
> > > > >
> > > > > >
> > > > > >    I'm guessing this goes back to inefficient packing from something
> > > > > >    like zbud, which would waste half a page on one repeating byte.
> > > > > >
> > > > > >    But zsmalloc can do 32 byte objects. It's also a batching slab
> > > > > >    allocator, where storing a series of small, same-sized objects is
> > > > > >    quite fast.
> > > > > >
> > > > > >    Add to that the additional branches, the additional kmap, the extra
> > > > > >    scanning of every single page for patterns - all in the fast path
> > > > > >    of zswap, when we already know that the vast majority of incoming
> > > > > >    pages will need to be properly compressed anyway.
> > > > > >
> > > > > >    Maybe it's time to get rid of the special handling entirely?
> > > > >
> > > > > We would still be wasting some memory (~96 bytes between zswap_entry
> > > > > and zsmalloc object), and wasting cycling allocating them. This could
> > > > > be made up for by cycles saved by removing the handling. We will be
> > > > > saving some branches for sure. I am not worried about kmap as I think
> > > > > it's a noop in most cases.
> > > >
> > > > Yes, true.
> > > >
> > > > > I am interested to see how much we could save by removing scanning for
> > > > > patterns. We may not save much if we abort after reading a few words
> > > > > in most cases, but I guess we could also be scanning a considerable
> > > > > amount before aborting. On the other hand, we would be reading the
> > > > > page contents into cache anyway for compression, so maybe it doesn't
> > > > > really matter?
> > > > >
> > > > > I will try to collect some data about this. I will start by trying to
> > > > > find out how the compression algorithms handle same-filled pages. If
> > > > > they can compress it efficiently, then I will try to get more data on
> > > > > the tradeoff from removing the handling.
> > > >
> > > > I do wonder if this could be overthinking it, too.
> > > >
> > > > Double checking the numbers on our fleet, a 96 additional bytes for
> > > > each same-filled entry would result in a
> > > >
> > > > 1) p50 waste of 0.008% of total memory, and a
> > > >
> > > > 2) p99 waste of 0.06% of total memory.
> >
> > Right. Assuming the compressors do not surprise us and store
> > same-filled pages in an absurd way, it's not worth it in terms of
> > memory savings.
> >
> > > >
> > > > And this is without us having even thought about trying to make
> > > > zsmalloc more efficient for this particular usecase - which might be
> > > > the better point of attack, if we think it's actually worth it.
> > > >
> > > > So my take is that unless removing it would be outright horrible from
> > > > a %sys POV (which seems pretty unlikely), IMO it would be fine to just
> > > > delete it entirely with a "not worth the maintenance cost" argument.
> > > >
> > > > If you turn the argument around, and somebody would submit the code as
> > > > it is today, with the numbers being what they are above, I'm not sure
> > > > we would even accept it!
> > >
> > > The context guy is here :)
> > >
> > > Not arguing for one way or another, but I did find the original patch
> > > that introduced same filled page handling:
> > >
> > > https://github.com/torvalds/linux/commit/a85f878b443f8d2b91ba76f09da21ac0af22e07f
> > >
> > > https://lore.kernel.org/all/20171018104832epcms5p1b2232e2236258de3d03d1344dde9fce0@epcms5p1/T/#u
> >
> > Thanks for digging this up. I don't know why I didn't start there :)
> >
> > Following in your footsteps, and given that zram has the same feature,
> > I found the patch that added support for non-zero same-filled pages in
> > zram:
> > https://lore.kernel.org/all/[e-mail]/#t
> >
> > Both of them confirm that most same-filled pages are zero pages, but
> > they show a more significant portion of same-filled pages being
> > non-zero (17% to 40%). I suspect this will be less in data centers
> > compared to consumer apps.
> >
> > The zswap patch also reports significant performance improvements from
> > the same-filled handling, but this is with 17-22% same-filled pages.
> > Johannes mentioned around 10% in your data centers, so the performance
> > improvement would be less. In the kernel build tests I ran with only
> > around 1.5% same-filled pages I observed 1.4% improvements just by
> > optimizing them (only zero-filled, skipping allocations).
> >
> > So I think removing the same-filled pages handling completely may be
> > too aggressive, because it doesn't only affect the memory efficiency,
> > but also cycles spent when handling those pages. Just avoiding going
> > through the allocator and compressor has to account for something :)
> 
> Here is another data point. I tried removing the same-filled handling
> code completely with the diff Johannes sent upthread. I saw 1.3%
> improvement in the kernel build test, very similar to the improvement
> from this patch series. _However_, the kernel build test only produces
> ~1.5% zero-filled pages in my runs. More realistic workloads have
> significantly higher percentages as demonstrated upthread.
> 
> In other words, the kernel build test (at least in my runs) seems to
> be the worst case scenario for same-filled/zero-filled pages. Since
> the improvement from removing same-filled handling is quite small in
> this case, I suspect there will be no improvement, but possibly a
> regression, on real workloads.
> 
> As the zero-filled pages ratio increases:
> - The performance with this series will improve.
> - The performance with removing same-filled handling completely will
> become worse.

Sorry, this thread is still really lacking practical perspective.

As do the numbers that initially justified the patch. Sure, the stores
of same-filled pages are faster. What's the cost of prechecking 90% of
the other pages that need compression?

Also, this is the swap path we're talking about. There is vmscan, swap
slot allocations, page table walks, TLB flushes, zswap tree inserts;
then a page fault and everything in reverse.

I perf'd zswapping out data that is 10% same-filled and 90% data that
always needs compression. It does nothing but madvise(MADV_PAGEOUT),
and the zswap_store() stack is already only ~60% of the cycles.

Using zsmalloc + zstd, this is the diff between vanilla and my patch:

# Baseline  Delta Abs  Shared Object         Symbol
# ........  .........  ....................  .....................................................
#
     4.34%     -3.02%  [kernel.kallsyms]     [k] zswap_store
    11.07%     +1.41%  [kernel.kallsyms]     [k] ZSTD_compressBlock_doubleFast
    15.55%     +0.91%  [kernel.kallsyms]     [k] FSE_buildCTable_wksp

As expected, we have to compress a bit more; on the other hand we're
removing the content scan for same-filled for 90% of the pages that
don't benefit from it. They almost amortize each other. Let's round it
up and the remaining difference is ~1%.

It's difficult to make the case that this matters to any real
workloads with actual think time in between paging.

But let's say you do make the case that zero-filled pages are worth
optimizing for. Why is this in zswap? Why not do it in vmscan with a
generic zero-swp_entry_t, and avoid the swap backend altogether? No
swap slot allocation, no zswap tree, no *IO on disk swap*.

However you slice it, I fail to see how this has a place in
zswap. It's trying to optimize the slow path of a slow path, at the
wrong layer of the reclaim stack.

Yosry Ahmed March 29, 2024, 6:56 p.m. UTC | #13

[..]
> > > > The context guy is here :)
> > > >
> > > > Not arguing for one way or another, but I did find the original patch
> > > > that introduced same filled page handling:
> > > >
> > > > https://github.com/torvalds/linux/commit/a85f878b443f8d2b91ba76f09da21ac0af22e07f
> > > >
> > > > https://lore.kernel.org/all/20171018104832epcms5p1b2232e2236258de3d03d1344dde9fce0@epcms5p1/T/#u
> > >
> > > Thanks for digging this up. I don't know why I didn't start there :)
> > >
> > > Following in your footsteps, and given that zram has the same feature,
> > > I found the patch that added support for non-zero same-filled pages in
> > > zram:
> > > https://lore.kernel.org/all/[e-mail]/#t
> > >
> > > Both of them confirm that most same-filled pages are zero pages, but
> > > they show a more significant portion of same-filled pages being
> > > non-zero (17% to 40%). I suspect this will be less in data centers
> > > compared to consumer apps.
> > >
> > > The zswap patch also reports significant performance improvements from
> > > the same-filled handling, but this is with 17-22% same-filled pages.
> > > Johannes mentioned around 10% in your data centers, so the performance
> > > improvement would be less. In the kernel build tests I ran with only
> > > around 1.5% same-filled pages I observed 1.4% improvements just by
> > > optimizing them (only zero-filled, skipping allocations).
> > >
> > > So I think removing the same-filled pages handling completely may be
> > > too aggressive, because it doesn't only affect the memory efficiency,
> > > but also cycles spent when handling those pages. Just avoiding going
> > > through the allocator and compressor has to account for something :)
> >
> > Here is another data point. I tried removing the same-filled handling
> > code completely with the diff Johannes sent upthread. I saw 1.3%
> > improvement in the kernel build test, very similar to the improvement
> > from this patch series. _However_, the kernel build test only produces
> > ~1.5% zero-filled pages in my runs. More realistic workloads have
> > significantly higher percentages as demonstrated upthread.
> >
> > In other words, the kernel build test (at least in my runs) seems to
> > be the worst case scenario for same-filled/zero-filled pages. Since
> > the improvement from removing same-filled handling is quite small in
> > this case, I suspect there will be no improvement, but possibly a
> > regression, on real workloads.
> >
> > As the zero-filled pages ratio increases:
> > - The performance with this series will improve.
> > - The performance with removing same-filled handling completely will
> > become worse.
>
> Sorry, this thread is still really lacking practical perspective.
>
> As do the numbers that initially justified the patch. Sure, the stores
> of same-filled pages are faster. What's the cost of prechecking 90% of
> the other pages that need compression?

Well, that's exactly what I was trying to find out :)

The kernel build test has over 98% pages that are not same-filled in
my runs, so we are paying the cost of prechecking 98% of pages for
same-filled contents needlessly. However, removing same-filled
handling only resulted in a 1.4% performance improvement. We should
expect even less for workloads that have 90% non-same-filled pages,
right?

It seems like the cost of prechecking is not that bad at all,
potentially because the page contents are read into cache anyway. Did
I miss something?

>
> Also, this is the swap path we're talking about. There is vmscan, swap
> slot allocations, page table walks, TLB flushes, zswap tree inserts;
> then a page fault and everything in reverse.
>
> I perf'd zswapping out data that is 10% same-filled and 90% data that
> always needs compression. It does nothing but madvise(MADV_PAGEOUT),
> and the zswap_store() stack is already only ~60% of the cycles.
>
> Using zsmalloc + zstd, this is the diff between vanilla and my patch:
>
> # Baseline  Delta Abs  Shared Object         Symbol
> # ........  .........  ....................  .....................................................
> #
>      4.34%     -3.02%  [kernel.kallsyms]     [k] zswap_store
>     11.07%     +1.41%  [kernel.kallsyms]     [k] ZSTD_compressBlock_doubleFast
>     15.55%     +0.91%  [kernel.kallsyms]     [k] FSE_buildCTable_wksp
>
> As expected, we have to compress a bit more; on the other hand we're
> removing the content scan for same-filled for 90% of the pages that
> don't benefit from it. They almost amortize each other. Let's round it
> up and the remaining difference is ~1%.

Thanks for the data, this is very useful.

There is also the load path. The original patch that introduced
same-filled pages reports more gains on the load side, which also
happens to be more latency-sensitive. Of course, the data could be
outdated -- but it's a different type of workload than what will be
running in a data center fleet AFAICT.

Is there also no noticeable difference on the load side in your data?

Also, how much increase did you observe in the size of compressed data
with your patch? Just curious about how zstd ended up handling those
pages.

>
> It's difficult to make the case that this matters to any real
> workloads with actual think time in between paging.

If the difference in performance is 1%, I surely agree.

The patch reported 19-32% improvement in store time for same-filled
pages depending on the workload and platform. For 10% same-filled
pages, this should roughly correspond to 2-3% overall improvement,
which is not too far from the 1% you observed.

The patch reported much larger improvement for load times (which
matters more), 49-85% for same-filled pages. If this corresponds to
5-8% overall improvement in zswap load time for a workload with 10%
same-filled pages, that would be very significant. I don't expect to
see such improvements tbh, but we should check.

Let's CC Srividya here for visibility.

>
> But let's say you do make the case that zero-filled pages are worth
> optimizing for.

I am not saying they are for sure, but removing the same-filled
checking didn't seem to improve performance much in my testing, so the
cost seems to be mostly in maintenance. This makes it seem to me that
it *could* be a good tradeoff to only handle zero-filled pages. We can
make them slightly faster and we can trim the complexity -- as shown
by this patch.

> Why is this in zswap? Why not do it in vmscan with a
> generic zero-swp_entry_t, and avoid the swap backend altogether? No
> swap slot allocation, no zswap tree, no *IO on disk swap*.

That part I definitely agree with, especially that the logic is
duplicated in zram.

>
> However you slice it, I fail to see how this has a place in
> zswap. It's trying to optimize the slow path of a slow path, at the
> wrong layer of the reclaim stack.

Agreeing for the store path, we still need some clarity on the load
path. But yeah all-in-all zswap is not the correct place for such
optimizations, but it's the way the handling currently lives.

Johannes Weiner March 29, 2024, 9:17 p.m. UTC | #14

On Fri, Mar 29, 2024 at 11:56:46AM -0700, Yosry Ahmed wrote:
> > I perf'd zswapping out data that is 10% same-filled and 90% data that
> > always needs compression. It does nothing but madvise(MADV_PAGEOUT),
> > and the zswap_store() stack is already only ~60% of the cycles.
> >
> > Using zsmalloc + zstd, this is the diff between vanilla and my patch:
> >
> > # Baseline  Delta Abs  Shared Object         Symbol
> > # ........  .........  ....................  .....................................................
> > #
> >      4.34%     -3.02%  [kernel.kallsyms]     [k] zswap_store
> >     11.07%     +1.41%  [kernel.kallsyms]     [k] ZSTD_compressBlock_doubleFast
> >     15.55%     +0.91%  [kernel.kallsyms]     [k] FSE_buildCTable_wksp
> >
> > As expected, we have to compress a bit more; on the other hand we're
> > removing the content scan for same-filled for 90% of the pages that
> > don't benefit from it. They almost amortize each other. Let's round it
> > up and the remaining difference is ~1%.
> 
> Thanks for the data, this is very useful.
> 
> There is also the load path. The original patch that introduced
> same-filled pages reports more gains on the load side, which also
> happens to be more latency-sensitive. Of course, the data could be
> outdated -- but it's a different type of workload than what will be
> running in a data center fleet AFAICT.
> 
> Is there also no noticeable difference on the load side in your data?

     9.40%     +2.51%  [kernel.kallsyms]  [k] ZSTD_safecopy
     0.76%     -0.48%  [kernel.kallsyms]  [k] zswap_load

About 2% net.

Checking other compression algorithms, lzo eats 27.58%, and lz4
13.82%. The variance between these alone makes our "try to be smarter
than an actual compression algorithm" code look even sillier.

> Also, how much increase did you observe in the size of compressed data
> with your patch? Just curious about how zstd ended up handling those
> pages.

Checking zsmalloc stats, it did pack the same-filled ones down into 32
byte objects. So 0.7% of their original size. That's negligible, even
for workloads that have an unusually high share of them.

> > It's difficult to make the case that this matters to any real
> > workloads with actual think time in between paging.
> 
> If the difference in performance is 1%, I surely agree.
> 
> The patch reported 19-32% improvement in store time for same-filled
> pages depending on the workload and platform. For 10% same-filled
> pages, this should roughly correspond to 2-3% overall improvement,
> which is not too far from the 1% you observed.

Right.

> The patch reported much larger improvement for load times (which
> matters more), 49-85% for same-filled pages. If this corresponds to
> 5-8% overall improvement in zswap load time for a workload with 10%
> same-filled pages, that would be very significant. I don't expect to
> see such improvements tbh, but we should check.

No, I'm seeing around 2% net.

> > But let's say you do make the case that zero-filled pages are worth
> > optimizing for.
> 
> I am not saying they are for sure, but removing the same-filled
> checking didn't seem to improve performance much in my testing, so the
> cost seems to be mostly in maintenance. This makes it seem to me that
> it *could* be a good tradeoff to only handle zero-filled pages. We can
> make them slightly faster and we can trim the complexity -- as shown
> by this patch.

In the original numbers, there was a certain percentage of non-zero
same-filled pages. You still first have to find that number for real
production loads to determine what the tradeoff actually is.

And I disagree that the code is less complex. There are fewer lines to
the memchr_inv() than to the open-coded word-scan, but that scan is
dead simple, self-contained and out of the way.

So call that a wash in terms of maintenance burden, but for a
reduction in functionality and a regression risk (however small).

The next patch to store them as special xarray entries is also a wash
at best. It trades the entry having an implicit subtype for no type at
all. zswap_load_zero_filled() looks like it's the fast path, and
decompression the fallback; the entry destructor is now called
"zswap_tree_free_element" and takes a void pointer. It also re-adds
most of the lines deleted by the zero-only patch.

I think this is actually a bit worse than the status quo.

But my point is, this all seems like a lot of opportunity cost in
terms of engineering time, review bandwidth, regression risk, and
readability, hackability, reliability, predictability of the code -
for gains that are still not shown to actually matter in practice.

https://lore.kernel.org/all/[e-mail]/

This needs numbers to show not just that your patches are fine, but
that any version of this optimization actually matters for real
workloads. Without that, my vote would be NAK.

Yosry Ahmed March 29, 2024, 10:29 p.m. UTC | #15

On Fri, Mar 29, 2024 at 2:17 PM Johannes Weiner <[e-mail]> wrote:
>
> On Fri, Mar 29, 2024 at 11:56:46AM -0700, Yosry Ahmed wrote:
> > > I perf'd zswapping out data that is 10% same-filled and 90% data that
> > > always needs compression. It does nothing but madvise(MADV_PAGEOUT),
> > > and the zswap_store() stack is already only ~60% of the cycles.
> > >
> > > Using zsmalloc + zstd, this is the diff between vanilla and my patch:
> > >
> > > # Baseline  Delta Abs  Shared Object         Symbol
> > > # ........  .........  ....................  .....................................................
> > > #
> > >      4.34%     -3.02%  [kernel.kallsyms]     [k] zswap_store
> > >     11.07%     +1.41%  [kernel.kallsyms]     [k] ZSTD_compressBlock_doubleFast
> > >     15.55%     +0.91%  [kernel.kallsyms]     [k] FSE_buildCTable_wksp
> > >
> > > As expected, we have to compress a bit more; on the other hand we're
> > > removing the content scan for same-filled for 90% of the pages that
> > > don't benefit from it. They almost amortize each other. Let's round it
> > > up and the remaining difference is ~1%.
> >
> > Thanks for the data, this is very useful.
> >
> > There is also the load path. The original patch that introduced
> > same-filled pages reports more gains on the load side, which also
> > happens to be more latency-sensitive. Of course, the data could be
> > outdated -- but it's a different type of workload than what will be
> > running in a data center fleet AFAICT.
> >
> > Is there also no noticeable difference on the load side in your data?
>
>      9.40%     +2.51%  [kernel.kallsyms]  [k] ZSTD_safecopy
>      0.76%     -0.48%  [kernel.kallsyms]  [k] zswap_load
>
> About 2% net.
>
> Checking other compression algorithms, lzo eats 27.58%, and lz4
> 13.82%. The variance between these alone makes our "try to be smarter
> than an actual compression algorithm" code look even sillier.
>
> > Also, how much increase did you observe in the size of compressed data
> > with your patch? Just curious about how zstd ended up handling those
> > pages.
>
> Checking zsmalloc stats, it did pack the same-filled ones down into 32
> byte objects. So 0.7% of their original size. That's negligible, even
> for workloads that have an unusually high share of them.

Glad to see that this was handled appropriately.

>
> > > It's difficult to make the case that this matters to any real
> > > workloads with actual think time in between paging.
> >
> > If the difference in performance is 1%, I surely agree.
> >
> > The patch reported 19-32% improvement in store time for same-filled
> > pages depending on the workload and platform. For 10% same-filled
> > pages, this should roughly correspond to 2-3% overall improvement,
> > which is not too far from the 1% you observed.
>
> Right.
>
> > The patch reported much larger improvement for load times (which
> > matters more), 49-85% for same-filled pages. If this corresponds to
> > 5-8% overall improvement in zswap load time for a workload with 10%
> > same-filled pages, that would be very significant. I don't expect to
> > see such improvements tbh, but we should check.
>
> No, I'm seeing around 2% net.

You mentioned that other compressors eat more cycles in this case, so
perhaps the data in the original patch comes from one of those
compressors.

>
> > > But let's say you do make the case that zero-filled pages are worth
> > > optimizing for.
> >
> > I am not saying they are for sure, but removing the same-filled
> > checking didn't seem to improve performance much in my testing, so the
> > cost seems to be mostly in maintenance. This makes it seem to me that
> > it *could* be a good tradeoff to only handle zero-filled pages. We can
> > make them slightly faster and we can trim the complexity -- as shown
> > by this patch.
>
> In the original numbers, there was a certain percentage of non-zero
> same-filled pages. You still first have to find that number for real
> production loads to determine what the tradeoff actually is.
>
> And I disagree that the code is less complex. There are fewer lines to
> the memchr_inv() than to the open-coded word-scan, but that scan is
> dead simple, self-contained and out of the way.
>
> So call that a wash in terms of maintenance burden, but for a
> reduction in functionality and a regression risk (however small).
>
> The next patch to store them as special xarray entries is also a wash
> at best. It trades the entry having an implicit subtype for no type at
> all. zswap_load_zero_filled() looks like it's the fast path, and
> decompression the fallback; the entry destructor is now called
> "zswap_tree_free_element" and takes a void pointer. It also re-adds
> most of the lines deleted by the zero-only patch.
>
> I think this is actually a bit worse than the status quo.
>
> But my point is, this all seems like a lot of opportunity cost in
> terms of engineering time, review bandwidth, regression risk, and
> readability, hackability, reliability, predictability of the code -
> for gains that are still not shown to actually matter in practice.

Yeah in terms of code cleanliness it did not turn out as I thought it
would. Actually even using different subtypes will have either
similarly abstract (yet less clear) helpers, or completely separate
paths with code duplication -- both of which are not ideal. So perhaps
it's better to leave it alone (and perhaps clean it up slightly) or
remove it completely.

I wanted to see what others thought, and I was aware it's
controversial (hence RFC) :)

Anyway, I will send a separate series with only cleanups and removing
knobs. We can discuss completely removing same-filled handling
separately. I suspect 2% regression in the load path (and potentially
larger with other compressors) may not be okay.

If handling for zero-filled pages is added directly in reclaim as you
suggested though, then the justification for handling other patterns
in zswap becomes much less :) Handling it in reclaim also means we
avoid IO for zero pages completely, which would be even more
beneficial than just avoiding compression/decompression in zswap.

>
> https://lore.kernel.org/all/[e-mail]/
>
> This needs numbers to show not just that your patches are fine, but
> that any version of this optimization actually matters for real
> workloads. Without that, my vote would be NAK.

Patch

diff --git a/mm/zswap.c b/mm/zswap.c
index 0fc27ae950c74..413d9242cf500 100644
--- a/mm/zswap.c
+++ b/mm/zswap.c
@@ -44,8 +44,8 @@ 
 **********************************/
 /* The number of compressed pages currently stored in zswap */
 atomic_t zswap_stored_pages = ATOMIC_INIT(0);
-/* The number of same-value filled pages currently stored in zswap */
-static atomic_t zswap_same_filled_pages = ATOMIC_INIT(0);
+/* The number of zero-filled pages currently stored in zswap */
+static atomic_t zswap_zero_filled_pages = ATOMIC_INIT(0);
 
 /*
  * The statistics below are not protected from concurrent access for
@@ -123,9 +123,9 @@  static unsigned int zswap_accept_thr_percent = 90; /* of max pool size */
 module_param_named(accept_threshold_percent, zswap_accept_thr_percent,
 		   uint, 0644);
 
-/* Enable/disable handling non-same-value filled pages (enabled by default) */
-static bool zswap_non_same_filled_pages_enabled = true;
-module_param_named(non_same_filled_pages_enabled, zswap_non_same_filled_pages_enabled,
+/* Enable/disable handling non-zero-filled pages (enabled by default) */
+static bool zswap_non_zero_filled_pages_enabled = true;
+module_param_named(non_same_filled_pages_enabled, zswap_non_zero_filled_pages_enabled,
 		   bool, 0644);
 
 /* Number of zpools in zswap_pool (empirically determined for scalability) */
@@ -187,11 +187,10 @@  static struct shrinker *zswap_shrinker;
  *
  * swpentry - associated swap entry, the offset indexes into the red-black tree
  * length - the length in bytes of the compressed page data.  Needed during
- *          decompression. For a same value filled page length is 0, and both
+ *          decompression. For a zero-filled page length is 0, and both
  *          pool and lru are invalid and must be ignored.
  * pool - the zswap_pool the entry's data is in
  * handle - zpool allocation handle that stores the compressed page data
- * value - value of the same-value filled pages which have same content
  * objcg - the obj_cgroup that the compressed memory is charged to
  * lru - handle to the pool's lru used to evict pages.
  */
@@ -199,10 +198,7 @@  struct zswap_entry {
 	swp_entry_t swpentry;
 	unsigned int length;
 	struct zswap_pool *pool;
-	union {
-		unsigned long handle;
-		unsigned long value;
-	};
+	unsigned long handle;
 	struct obj_cgroup *objcg;
 	struct list_head lru;
 };
@@ -805,7 +801,7 @@  static struct zpool *zswap_find_zpool(struct zswap_entry *entry)
 static void zswap_entry_free(struct zswap_entry *entry)
 {
 	if (!entry->length)
-		atomic_dec(&zswap_same_filled_pages);
+		atomic_dec(&zswap_zero_filled_pages);
 	else {
 		zswap_lru_del(&zswap_list_lru, entry);
 		zpool_free(zswap_find_zpool(entry), entry->handle);
@@ -1377,43 +1373,17 @@  static void shrink_worker(struct work_struct *w)
 	} while (zswap_total_pages() > thr);
 }
 
-static bool zswap_is_folio_same_filled(struct folio *folio, unsigned long *value)
+static bool zswap_is_folio_zero_filled(struct folio *folio)
 {
-	unsigned long *page;
-	unsigned long val;
-	unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1;
+	unsigned long *kaddr;
 	bool ret;
 
-	page = kmap_local_folio(folio, 0);
-	val = page[0];
-
-	if (val != page[last_pos]) {
-		ret = false;
-		goto out;
-	}
-
-	for (pos = 1; pos < last_pos; pos++) {
-		if (val != page[pos]) {
-			ret = false;
-			goto out;
-		}
-	}
-
-	*value = val;
-	ret = true;
-out:
-	kunmap_local(page);
+	kaddr = kmap_local_folio(folio, 0);
+	ret = !memchr_inv(kaddr, 0, PAGE_SIZE);
+	kunmap_local(kaddr);
 	return ret;
 }
 
-static void zswap_fill_page(void *ptr, unsigned long value)
-{
-	unsigned long *page;
-
-	page = (unsigned long *)ptr;
-	memset_l(page, value, PAGE_SIZE / sizeof(unsigned long));
-}
-
 static bool zswap_check_limit(void)
 {
 	unsigned long cur_pages = zswap_total_pages();
@@ -1437,7 +1407,6 @@  bool zswap_store(struct folio *folio)
 	struct obj_cgroup *objcg = NULL;
 	struct mem_cgroup *memcg = NULL;
 	struct zswap_entry *entry;
-	unsigned long value;
 
 	VM_WARN_ON_ONCE(!folio_test_locked(folio));
 	VM_WARN_ON_ONCE(!folio_test_swapcache(folio));
@@ -1470,14 +1439,13 @@  bool zswap_store(struct folio *folio)
 		goto reject;
 	}
 
-	if (zswap_is_folio_same_filled(folio, &value)) {
+	if (zswap_is_folio_zero_filled(folio)) {
 		entry->length = 0;
-		entry->value = value;
-		atomic_inc(&zswap_same_filled_pages);
+		atomic_inc(&zswap_zero_filled_pages);
 		goto insert_entry;
 	}
 
-	if (!zswap_non_same_filled_pages_enabled)
+	if (!zswap_non_zero_filled_pages_enabled)
 		goto freepage;
 
 	/* if entry is successfully added, it keeps the reference */
@@ -1532,7 +1500,7 @@  bool zswap_store(struct folio *folio)
 
 store_failed:
 	if (!entry->length)
-		atomic_dec(&zswap_same_filled_pages);
+		atomic_dec(&zswap_zero_filled_pages);
 	else {
 		zpool_free(zswap_find_zpool(entry), entry->handle);
 put_pool:
@@ -1563,7 +1531,6 @@  bool zswap_load(struct folio *folio)
 	struct page *page = &folio->page;
 	struct xarray *tree = swap_zswap_tree(swp);
 	struct zswap_entry *entry;
-	u8 *dst;
 
 	VM_WARN_ON_ONCE(!folio_test_locked(folio));
 
@@ -1573,11 +1540,8 @@  bool zswap_load(struct folio *folio)
 
 	if (entry->length)
 		zswap_decompress(entry, page);
-	else {
-		dst = kmap_local_page(page);
-		zswap_fill_page(dst, entry->value);
-		kunmap_local(dst);
-	}
+	else
+		clear_highpage(page);
 
 	count_vm_event(ZSWPIN);
 	if (entry->objcg)
@@ -1679,7 +1643,7 @@  static int zswap_debugfs_init(void)
 	debugfs_create_atomic_t("stored_pages", 0444,
 				zswap_debugfs_root, &zswap_stored_pages);
 	debugfs_create_atomic_t("same_filled_pages", 0444,
-				zswap_debugfs_root, &zswap_same_filled_pages);
+				zswap_debugfs_root, &zswap_zero_filled_pages);
 
 	return 0;
 }