Hi xiang,
On 2019/7/3 14:06, Gao Xiang wrote:
> Hi Chao,
>
> On 2019/7/3 10:09, Gao Xiang wrote:
>>
>>
>> On 2019/7/3 9:50, Chao Yu wrote:
>>> On 2019/7/1 2:58, Gao Xiang wrote:
>>>> From: Gao Xiang <gaoxiang25@xxxxxxxxxx>
>>>>
>>>> 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: 7fc45dbc938a ("staging: erofs: introduce generic decompression backend")
>>>> Signed-off-by: Gao Xiang <gaoxiang25@xxxxxxxxxx>
>>>> ---
>>>> drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
>>>> 1 file changed, 28 insertions(+), 22 deletions(-)
>>>>
>>>> diff --git a/drivers/staging/erofs/decompressor.c b/drivers/staging/erofs/decompressor.c
>>>> index 80f1f39719ba..1fb0abb98dff 100644
>>>> --- a/drivers/staging/erofs/decompressor.c
>>>> +++ b/drivers/staging/erofs/decompressor.c
>>>> @@ -13,7 +13,7 @@
>>>> #define LZ4_DISTANCE_MAX 65535 /* set to maximum value by default */
>>>> #endif
>>>>
>>>> -#define LZ4_MAX_DISTANCE_PAGES DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE)
>>>> +#define LZ4_MAX_DISTANCE_PAGES (DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1)
>>>> #ifndef LZ4_DECOMPRESS_INPLACE_MARGIN
>>>> #define LZ4_DECOMPRESS_INPLACE_MARGIN(srcsize) (((srcsize) >> 8) + 32)
>>>> #endif
>>>> @@ -35,19 +35,28 @@ static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq,
>>>> const unsigned int nr =
>>>> PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
>>>> struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL };
>>>> - unsigned long unused[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES,
>>>> - BITS_PER_LONG)] = { 0 };
>>>> + unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES,
>>>> + BITS_PER_LONG)] = { 0 };
>>>> void *kaddr = NULL;
>>>> - unsigned int i, j, k;
>>>> + unsigned int i, j, top;
>>>>
>>>> - for (i = 0; i < nr; ++i) {
>>>> + top = 0;
>>>> + for (i = j = 0; i < nr; ++i, ++j) {
>>>> struct page *const page = rq->out[i];
>>>> + struct page *victim;
>>>>
>>>> - j = i & (LZ4_MAX_DISTANCE_PAGES - 1);
>>>> - if (availables[j])
>>>> - __set_bit(j, unused);
>>>> + if (j >= LZ4_MAX_DISTANCE_PAGES)
>>>> + j = 0;
>>>> +
>>>> + /* 'valid' bounced can only be tested after a complete round */
>>>> + if (test_bit(j, bounced)) {
>>>> + DBG_BUGON(i < LZ4_MAX_DISTANCE_PAGES);
>>>> + DBG_BUGON(top >= LZ4_MAX_DISTANCE_PAGES);
>>>> + availables[top++] = rq->out[i - LZ4_MAX_DISTANCE_PAGES];
>>>
>>> Maybe we can change 'i - LZ4_MAX_DISTANCE_PAGES' to 'j' directly for better
>>> readability.
>>
>> OK, I think they are equivalent as well, will change for readability, retest and resend.
>> Thanks for your suggestion :)
>
> I tested again and I observed that using j broke the logic and I think we cannot use j
> to replace i - LZ4_MAX_DISTANCE_PAGES.
>
> Since bounced pages was marked according to the last round rather than the first round,
> we cannot directly use the first round pages to push into the stack, e.g.
Yes, I can understand that, so the bitmap only indicate page in previous round
is a new bounced page or a referenced bounced page, using page at last round is
safe.
Anyway, thanks for the explanation below, and go ahead with current
implementation. :)
Thanks,
>
> 1)
> 0 1 2 ... 16 17 18 ... 33 34
> p b b
>
> bounce page could be allocated from rq->out[17], and we could reuse it from rq->out[34], which
> is not equal to rq->out[0].
>
> 2)
> 0 1 2 ... 16 17 18 19 ... 33 34 35 36
> b p b b
> allocated in rq->out[1] j = 1, reuse it in rq->out[19] j = 2, reuse it again in rq->out[36] j = 2,
> which is not equal to rq->out[2].
>
> I think the original patch is ok, and it cannot be replaced to rq->out[j].
>
> Thanks,
> Gao Xiang
>
>>
>> Thanks,
>> Gao Xiang
>>
>>>
>>> Otherwise, it looks good to me.
>>>
>>> Reviewed-by: Chao Yu <yuchao0@xxxxxxxxxx>
>>>
>>> Thanks,
>>>
>>>> + }
>>>>
>>>> if (page) {
>>>> + __clear_bit(j, bounced);
>>>> if (kaddr) {
>>>> if (kaddr + PAGE_SIZE == page_address(page))
>>>> kaddr += PAGE_SIZE;
>>>> @@ -59,27 +68,24 @@ static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq,
>>>> continue;
>>>> }
>>>> kaddr = NULL;
>>>> + __set_bit(j, bounced);
>>>>
>>>> - k = find_first_bit(unused, LZ4_MAX_DISTANCE_PAGES);
>>>> - if (k < LZ4_MAX_DISTANCE_PAGES) {
>>>> - j = k;
>>>> - get_page(availables[j]);
>>>> + if (top) {
>>>> + victim = availables[--top];
>>>> + get_page(victim);
>>>> } else {
>>>> - DBG_BUGON(availables[j]);
>>>> -
>>>> if (!list_empty(pagepool)) {
>>>> - availables[j] = lru_to_page(pagepool);
>>>> - list_del(&availables[j]->lru);
>>>> - DBG_BUGON(page_ref_count(availables[j]) != 1);
>>>> + victim = lru_to_page(pagepool);
>>>> + list_del(&victim->lru);
>>>> + DBG_BUGON(page_ref_count(victim) != 1);
>>>> } else {
>>>> - availables[j] = alloc_pages(GFP_KERNEL, 0);
>>>> - if (!availables[j])
>>>> + victim = alloc_pages(GFP_KERNEL, 0);
>>>> + if (!victim)
>>>> return -ENOMEM;
>>>> }
>>>> - availables[j]->mapping = Z_EROFS_MAPPING_STAGING;
>>>> + victim->mapping = Z_EROFS_MAPPING_STAGING;
>>>> }
>>>> - rq->out[i] = availables[j];
>>>> - __clear_bit(j, unused);
>>>> + rq->out[i] = victim;
>>>> }
>>>> return kaddr ? 1 : 0;
>>>> }
>>>>
> .
>
_______________________________________________
devel mailing list
devel@xxxxxxxxxxxxxxxxxxxxxx
http://driverdev.linuxdriverproject.org/mailman/listinfo/driverdev-devel
