• Dave Rodgman's avatar
    lib/lzo: fix ambiguous encoding bug in lzo-rle · b5265c81
    Dave Rodgman authored
    In some rare cases, for input data over 32 KB, lzo-rle could encode two
    different inputs to the same compressed representation, so that
    decompression is then ambiguous (i.e.  data may be corrupted - although
    zram is not affected because it operates over 4 KB pages).
    
    This modifies the compressor without changing the decompressor or the
    bitstream format, such that:
    
     - there is no change to how data produced by the old compressor is
       decompressed
    
     - an old decompressor will correctly decode data from the updated
       compressor
    
     - performance and compression ratio are not affected
    
     - we avoid introducing a new bitstream format
    
    In testing over 12.8M real-world files totalling 903 GB, three files
    were affected by this bug.  I also constructed 37M semi-random 64 KB
    files totalling 2.27 TB, and saw no affected files.  Finally I tested
    over files constructed to contain each of the ~1024 possible bad input
    sequences; for all of these cases, updated lzo-rle worked correctly.
    
    There is no significant impact to performance or compression ratio.
    Signed-off-by: default avatarDave Rodgman <dave.rodgman@arm.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Cc: Mark Rutland <mark.rutland@arm.com>
    Cc: Dave Rodgman <dave.rodgman@arm.com>
    Cc: Willy Tarreau <w@1wt.eu>
    Cc: Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com>
    Cc: Markus F.X.J. Oberhumer <markus@oberhumer.com>
    Cc: Minchan Kim <minchan@kernel.org>
    Cc: Nitin Gupta <ngupta@vflare.org>
    Cc: Chao Yu <yuchao0@huawei.com>
    Cc: <stable@vger.kernel.org>
    Link: http://lkml.kernel.org/r/20200507100203.29785-1-dave.rodgman@arm.comSigned-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    b5265c81
lzo.txt 9.36 KB