linux-kernel - Question about extensions to lib/lz4

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

Message-ID: <20241119235727.GA26223@hu-cgoldswo-lv.qualcomm.com>
Date: Tue, 19 Nov 2024 15:58:39 -0800
From: Chris Goldsworthy <quic_cgoldswo@...cinc.com>
To: Andrew Morton <akpm@...ux-foundation.org>,
        Sergey Senozhatsky
	<senozhatsky@...omium.org>,
        Al Viro <viro@...iv.linux.org.uk>
CC: Yann Collet <yann.collet.73@...il.com>, <linux-kernel@...r.kernel.org>
Subject: Question about extensions to lib/lz4

Hi Folks,

Qualcomm is designing a LZ4 compression / decompression engine, with the goal of
being able to do single-pass operations (i.e. we only read input from DDR once
for compression and decompression). This is achieved by using buffers internal
to the engine that store:
 - For compression, the running literal we've encountered, which is used as a
   search buffer
 - For decompression, the last part of the running decompressed output we've
   produced

The outcome of using internal (and obviously fixed-size) buffers for the above,
whilst not making any changes to the LZ4 format, are as follows:
 - For compression, if we fail to produce a match after running out of input
   buffer space, compression will fail.
 - For decompression, if the copy offset for a given block extends beyond
   what we're holding in our buffer, decompression will fail

We don't want to constrain our HW as such whilst maintaining compatibility with
SW, and allow it to compress and decompress streams of arbitrary lengths.
Focusing on decompression for now, we've proposed an extension to LZ4 that would
allow SW to decompress streams compressed by HW like ours, which is described in
more detail here [1] in a Github discussion on the lz4 repository owned by Yann
Collet. The changes we've proposed are as follows, though we would want to add
a static branch check as well to remove overhead for those who do not want to
use this extension:

diff -rupN "torvalds linux master lib-lz4/lz4_decompress.c" lib-lz4-patched/lz4_decompress.c
--- "torvalds linux master lib-lz4/lz4_decompress.c"  2024-08-11 09:51:42.000000000 -0700
+++ lib-lz4-patched/lz4_decompress.c  2024-08-12 06:26:33.986693000 -0700
@@ -166,6 +166,7 @@ static FORCE_INLINE int LZ4_decompress_g
      ip += 2;
      match = op - offset;
      assert(match <= op); /* check overflow */
+      if (unlikely(!offset)) continue; /* skip copy with zero offset */

      /* Do not deal with overlapping matches. */
      if ((length != ML_MASK) &&
@@ -289,6 +290,7 @@ static FORCE_INLINE int LZ4_decompress_g
    offset = LZ4_readLE16(ip);
    ip += 2;
    match = op - offset;
+    if (unlikely(!offset)) continue; /* skip copy with zero offset */

    /* get matchlength */
    length = token & ML_MASK;

Yann Collet has indicated that these changes could be acceptable and implemented as
part of a LZ4 v2 block format, which would include several other changes as well
that have been proposed over the years. The timeline for making / socializing
this would be on the order of years though, if it does go through [1].

So our question is as follows: as part of submitting our driver, would it be
acceptable to take the above changes?

Thanks,

Chris.

[1] https://github.com/lz4/lz4/discussions/1517