1. 03 Jul, 2019 1 commit
    • Gao Xiang's avatar
      staging: erofs: fix LZ4 limited bounced page mis-reuse · af89bcef
      Gao Xiang authored
      Like all lz77-based algrithms, lz4 has a dynamically populated
      ("sliding window") dictionary and the maximum lookback distance
      is 65535. Therefore the number of bounced pages could be limited
      by erofs based on this property.
      
      However, just now we observed some lz4 sequences in the extreme
      case cannot be decompressed correctly after this feature is enabled,
      the root causes after analysis are clear as follows:
      1) max bounced pages should be 17 rather than 16 pages;
      2) considering the following case, the broken implementation
         could reuse unsafely in advance (in other words, reuse it
         less than a safe distance),
         0 1 2 ... 16 17 18 ... 33 34
         b             p  b         b
         note that the bounce page that we are concerned was allocated
         at 0, and it reused at 18 since page 17 exists, but it mis-reused
         at 34 in advance again, which causes decompress failure.
      
      This patch resolves the issue by introducing a bitmap to mark
      whether the page in the same position of last round is a bounced
      page or not, and a micro stack data structure to store all
      available bounced pages.
      
      Fixes: 7fc45dbc ("staging: erofs: introduce generic decompression backend")
      Reviewed-by: default avatarChao Yu <yuchao0@huawei.com>
      Signed-off-by: default avatarGao Xiang <gaoxiang25@huawei.com>
      Signed-off-by: default avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
      af89bcef
  2. 01 Jul, 2019 39 commits