linux-kernel - Re: [PATCH] lz4: Fix kernel decompression speed

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <0C67BA74-E014-449B-9E22-E0B1DDB930BF@fb.com>
Date:   Tue, 4 Aug 2020 02:57:50 +0000
From:   Nick Terrell <terrelln@...com>
To:     Arvind Sankar <nivedita@...m.mit.edu>
CC:     Nick Terrell <nickrterrell@...il.com>,
        Ingo Molnar <mingo@...nel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        X86 ML <x86@...nel.org>, Kernel Team <Kernel-team@...com>,
        Yann Collet <yann.collet.73@...il.com>,
        Gao Xiang <gaoxiang25@...wei.com>,
        Sven Schmidt <4sschmid@...ormatik.uni-hamburg.de>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Re: [PATCH] lz4: Fix kernel decompression speed



> On Aug 3, 2020, at 6:56 PM, Arvind Sankar <nivedita@...m.mit.edu> wrote:
> 
> On Mon, Aug 03, 2020 at 10:55:01PM +0000, Nick Terrell wrote:
>> 
>> 
>>> On Aug 3, 2020, at 2:57 PM, Arvind Sankar <nivedita@...m.mit.edu> wrote:
>>> 
>>> On Mon, Aug 03, 2020 at 12:40:22PM -0700, Nick Terrell wrote:
>>>> From: Nick Terrell <terrelln@...com>
>>>> 
>>>> This patch replaces all memcpy() calls with LZ4_memcpy() which calls
>>>> __builtin_memcpy() so the compiler can inline it.
>>>> 
>>>> LZ4 relies heavily on memcpy() with a constant size being inlined. In
>>>> x86 and i386 pre-boot environments memcpy() cannot be inlined because
>>>> memcpy() doesn't get defined as __builtin_memcpy().
>>>> 
>>>> An equivalent patch has been applied upstream so that the next import
>>>> won't lose this change [1].
>>>> 
>>>> I've measured the kernel decompression speed using QEMU before and after
>>>> this patch for the x86_64 and i386 architectures. The speed-up is about
>>>> 10x as shown below.
>>>> 
>>>> Code	Arch	Kernel Size	Time	Speed
>>>> v5.8	x86_64	11504832 B	148 ms	 79 MB/s
>>>> patch	x86_64	11503872 B	 13 ms	885 MB/s
>>>> v5.8	i386	 9621216 B	 91 ms	106 MB/s
>>>> patch	i386	 9620224 B	 10 ms	962 MB/s
>>>> 
>>>> I also measured the time to decompress the initramfs on x86_64, i386,
>>>> and arm. All three show the same decompression speed before and after,
>>>> as expected.
>>>> 
>>>> [1] https://github.com/lz4/lz4/pull/890
>>>> 
>>> 
>>> Hi Nick, would you be able to test the below patch's performance to
>>> verify it gives the same speedup? It removes the #undef in misc.c which
>>> causes the decompressors to not use the builtin version. It should be
>>> equivalent to yours except for applying it to all the decompressors.
>>> 
>>> Thanks.
>> 
>> I will measure it. I would expect it to provide the same speed up. It would be great to fix
>> the problem for x86/i386 in general.
> 
> Thanks. I tried using RDTSC to get some timings under QEMU, and I get
> similar speedup as you have for LZ4, and around 15-20% or so for ZSTD
> (on 64-bit)

By the way, I was using this script for performance testing [0].

> -- I see that ZSTD_copy8 is already using __builtin_memcpy,
> but there must be more that can be optimized? There's a couple 1/2-byte
> sized copies in huf_decompress.c.

Oh wow, I totally missed that, I guess I stopped looking once performance
was about what I expected, nice find!

I suspect it is mostly the memcpy inside of HUF_decodeSymbolX4(), since
that should be the only hot one [1].

Do you want to put up the patch to fix the memcpy’s in zstd Huffman, or should I?

I will be submitting a patch upstream to migrate all of zstd’s memcpy() calls to
use __builtin_memcpy(), since I plan on updating the version in the kernel to
upstream zstd in the next few months. I was waiting until the compressed kernel
patch set landed, so I didn't distract from it.

[0] https://gist.github.com/terrelln/9bd53321a669f62683c608af8944fbc2
[1] https://github.com/torvalds/linux/blob/master/lib/zstd/huf_decompress.c#L598

Best,
Nick