linux-kernel - Re: [PATCH] mm/zswap: try to avoid worst-case scenario on same element pages

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-Id: <20230226135734.6ba10ed872bc14802937c7ea@linux-foundation.org>
Date:   Sun, 26 Feb 2023 13:57:34 -0800
From:   Andrew Morton <akpm@...ux-foundation.org>
To:     Taejoon Song <taejoon.song@....com>
Cc:     sjenning@...hat.com, ddstreet@...e.org, vitaly.wool@...sulko.com,
        linux-mm@...ck.org, linux-kernel@...r.kernel.org, yjay.kim@....com,
        Sergey Senozhatsky <senozhatsky@...omium.org>,
        Minchan Kim <minchan@...nel.org>
Subject: Re: [PATCH] mm/zswap: try to avoid worst-case scenario on same
 element pages

On Mon,  6 Feb 2023 04:00:36 +0900 Taejoon Song <taejoon.song@....com> wrote:

> The worst-case scenario on finding same element pages is that almost all
> elements are same at the first glance but only last few elements are
> different.
> 
> Since the same element tends to be grouped from the beginning of the
> pages, if we check the first element with the last element before
> looping through all elements, we might have some chances to quickly
> detect non-same element pages.
> 
> 1. Test is done under LG webOS TV (64-bit arch)
> 2. Dump the swap-out pages (~819200 pages)
> 3. Analyze the pages with simple test script which counts the iteration
>    number and measures the speed at off-line
> 
> Under 64-bit arch, the worst iteration count is PAGE_SIZE / 8 bytes =
> 512.  The speed is based on the time to consume page_same_filled()
> function only.  The result, on average, is listed as below:
> 
>                                    Num of Iter    Speed(MB/s)
> Looping-Forward (Orig)                 38            99265
> Looping-Backward                       36           102725
> Last-element-check (This Patch)        33           125072
> 
> The result shows that the average iteration count decreases by 13% and
> the speed increases by 25% with this patch.  This patch does not
> increase the overall time complexity, though.
> 
> I also ran simpler version which uses backward loop. Just looping
> backward also makes some improvement, but less than this patch.

Seems a nice change.

> This patch was already applied to zram on mainline v5.6-rc1:
> https://lkml.org/lkml/2019/12/3/1422

I redid this a little:

A similar change has already been made to zram in 90f82cbfe502 ("zram: try
to avoid worst-case scenario on same element pages").

> ...
> --- a/mm/zswap.c
> +++ b/mm/zswap.c
> @@ -1073,15 +1073,23 @@ static int zswap_writeback_entry(struct zpool *pool, unsigned long handle)
>  
>  static int zswap_is_page_same_filled(void *ptr, unsigned long *value)
>  {
> -	unsigned int pos;
>  	unsigned long *page;
> +	unsigned long val;
> +	unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1;
>  
>  	page = (unsigned long *)ptr;
> -	for (pos = 1; pos < PAGE_SIZE / sizeof(*page); pos++) {
> -		if (page[pos] != page[0])
> +	val = page[0];
> +
> +	if (val != page[last_pos])
> +		return 0;
> +
> +	for (pos = 1; pos < last_pos; pos++) {
> +		if (val != page[pos])
>  			return 0;
>  	}
> -	*value = page[0];
> +
> +	*value = val;
> +
>  	return 1;
>  }