Skip to contentSkip to conversation

staging: erofs: fix LZ4 limited bounced page mis-reuse

PATCH In review Gao Xiang 3 participants 6 messages Jun 30, 2019 – Jul 3, 2019 Staging

lore
Share & tools
lore

Gao Xiang

author
#0 lore raw

PATCH 1/1 staging: erofs: fix LZ4 limited bounced page mis-reuse

From: Gao Xiang <[email protected]>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +28 -22
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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];
+		}
 
 		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;
 }
Signature · 1 line
2.17.1
Reviewed-by on v1 1/1
#1 lore raw
Quoted 63 lines · Gao Xiang

From: Gao Xiang <gaoxiang25 at huawei.com>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +7 -6
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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);

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 55

Quoted 10 lines
drivers/staging/erofs/decompressor.c +8 -2
-		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.

Otherwise, it looks good to me.

Reviewed-by Chao Yu <yuchao0 at huawei.com>

Thanks,

Quoted 47 lines
drivers/staging/erofs/decompressor.c +13 -14
+		}
 
 		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;
 }
#2 lore raw
Quoted 63 lines · Chao Yu
Quoted 62 lines · Gao Xiang

From: Gao Xiang <gaoxiang25 at huawei.com>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +7 -5
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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;
 
Quoted 14 lines

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 55

Quoted 11 lines
drivers/staging/erofs/decompressor.c +8 -3
-		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 :)

Thanks,
Gao Xiang

Quoted 54 lines

Otherwise, it looks good to me.

Reviewed-by Chao Yu <yuchao0 at huawei.com>

Thanks,

Quoted 47 lines
drivers/staging/erofs/decompressor.c +13 -14
+		}
 
 		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;
 }
#3 lore raw

Hi Chao,

Quoted 81 lines · Gao Xiang
Quoted 63 lines · Chao Yu
Quoted 62 lines · Gao Xiang

From: Gao Xiang <gaoxiang25 at huawei.com>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +7 -5
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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;
 
Quoted 14 lines

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 55

Quoted 11 lines
drivers/staging/erofs/decompressor.c +8 -3
-		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.

Quoted 2 lines

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.

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

Quoted 58 lines

Thanks,
Gao Xiang

Quoted 54 lines

Otherwise, it looks good to me.

Reviewed-by Chao Yu <yuchao0 at huawei.com>

Thanks,

Quoted 47 lines
drivers/staging/erofs/decompressor.c +13 -14
+		}
 
 		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;
 }
#4 lore raw

Hi xiang,

Quoted 84 lines · Gao Xiang

Hi Chao,

Quoted 81 lines · Gao Xiang
Quoted 77 lines · Chao Yu
Quoted 63 lines · Gao Xiang

From: Gao Xiang <gaoxiang25 at huawei.com>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +7 -6
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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);

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 55

Quoted 10 lines
drivers/staging/erofs/decompressor.c +8 -2
-		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.

Quoted 8 lines
Quoted 2 lines

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,

Quoted 79 lines

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

Quoted 50 lines

Thanks,
Gao Xiang

Quoted 46 lines

Otherwise, it looks good to me.

Reviewed-by Chao Yu <yuchao0 at huawei.com>

Thanks,

Quoted 39 lines
drivers/staging/erofs/decompressor.c +12 -12
+		}
 
 		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;
Quoted 8 lines
Quoted 8 lines

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 91

Quoted 8 lines
drivers/staging/erofs/decompressor.c +1 -2
 		}
-		rq->out[i] = availables[j];
-		__clear_bit(j, unused);
+		rq->out[i] = victim;
 	}
 	return kaddr ? 1 : 0;
 }

.

#5 lore raw
Quoted 96 lines · Chao Yu

Hi xiang,

Quoted 84 lines · Gao Xiang

Hi Chao,

Quoted 81 lines · Gao Xiang
Quoted 77 lines · Chao Yu
Quoted 63 lines · Gao Xiang

From: Gao Xiang <gaoxiang25 at huawei.com>

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 at huawei.com>
---
 drivers/staging/erofs/decompressor.c | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)
drivers/staging/erofs/decompressor.c +7 -6
index 80f1f39719ba..1fb0abb98dff 100644
@@ -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);

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 55

Quoted 10 lines
drivers/staging/erofs/decompressor.c +8 -2
-		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.

Quoted 8 lines
Quoted 2 lines

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.

Quoted 6 lines

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

Quoted 82 lines

Thanks,

Quoted 79 lines

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

Quoted 50 lines

Thanks,
Gao Xiang

Quoted 46 lines

Otherwise, it looks good to me.

Reviewed-by Chao Yu <yuchao0 at huawei.com>

Thanks,

Quoted 39 lines
drivers/staging/erofs/decompressor.c +12 -12
+		}
 
 		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;
Quoted 8 lines
Quoted 8 lines

drivers/staging/erofs/decompressor.c static int lz4_prepare_destpages(struct z_erofs_decompress_req *rq, · line 91

Quoted 8 lines
drivers/staging/erofs/decompressor.c +1 -2
 		}
-		rq->out[i] = availables[j];
-		__clear_bit(j, unused);
+		rq->out[i] = victim;
 	}
 	return kaddr ? 1 : 0;
 }

.