Re: [PATCH] staging: erofs: fix LZ4 limited bounced page mis-reuse

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 




On 2019/7/3 14:51, Chao Yu wrote:
> 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. :)

Yes, thanks for the idea and taking time to review :)

Thanks,
Gao Xiang

> 
> 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



[Index of Archives]     [Linux Driver Backports]     [DMA Engine]     [Linux GPIO]     [Linux SPI]     [Video for Linux]     [Linux USB Devel]     [Linux Coverity]     [Linux Audio Users]     [Linux Kernel]     [Linux SCSI]     [Yosemite Backpacking]
  Powered by Linux