linux-kernel - Re: [PATCH] zram: 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: <20191204225451.GA42672@google.com>
Date:   Wed, 4 Dec 2019 14:54:51 -0800
From:   Minchan Kim <minchan@...nel.org>
To:     Taejoon Song <taejoon.song@....com>,
        Andrew Morton <akpm@...ux-foundation.org>
Cc:     ngupta@...are.org, sergey.senozhatsky.work@...il.com,
        axboe@...nel.dk, linux-kernel@...r.kernel.org,
        linux-block@...r.kernel.org, yjay.kim@....com
Subject: Re: [PATCH] zram: try to avoid worst-case scenario on same element
 pages

On Wed, Dec 04, 2019 at 10:53:38AM +0900, Taejoon Song 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.
> 
> Signed-off-by: Taejoon Song <taejoon.song@....com>
Acked-by: Minchan Kim <minchan@...nel.org>

I think it's very reasonable optimization with small cost.