btrfs: lzo: Harden decompression callers to avoid kernel memory corruption.
v2 cover btrfs: lzo: Harden decompression callers to avoid kernel memory corruption.
This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/lzo_corruption
Which is based on v4.17-rc5.
James Harvey reported pretty strange kernel misbehavior where after reading certain btrfs compressed data, kernel crash with unrelated calltrace.
(https://bugzilla.kernel.org/show_bug.cgi?id=199707 and
https://www.spinics.net/lists/linux-btrfs/msg77971.html)
Thanks for his comprehensive debug help, we located the problem to:
1) Bad lzo decompression verification check
The direct cause.
The lzo decompression code involves memory copy for compressed data who crosses page boundary.
And if corrupted segment header contains invalid length, btrfs will do memory copy and then corrupt kernel memory.
Fix it by add header length check for each segment, and just in case, also add uncompressed data length check. (Patch 3)
The full explanation and kasan output can also be found in that patch.
2) Compressed extent created for NODATASUM inode
The root cause.
Will be addressed in another patchset.
Other patches are mostly cosmetic, like adding extra include for compression.h, to avoid later compiling error. (Patch 1)
Or adding comment of how btrfs organise its compressed data (Patch 2) And adding extra check for inlined compressed data even it's not really possible to happen (Patch 4)
Changelog:
v2:
Cosmetic updates. Mostly for comment and gramma. Comment and gramma fixes suggested by Nikolay. One 4 bytes <-> LE32 convert fixes in comment. Added reviewed-by tag for the 1st patch.
Qu Wenruo (4):
btrfs: compression: Add linux/sizes.h for compression.h
btrfs: lzo: Add comment about the how btrfs records its lzo compressed
data
btrfs: lzo: Add header length check to avoid slab out of bounds access
btrfs: lzo: Harden inline lzo compressed extent decompression
fs/btrfs/compression.h | 1 + fs/btrfs/lzo.c | 63 +++++++++++++++++++++++++++++++++++++++++- 2 files changed, 63 insertions(+), 1 deletion(-)
Signature · 1 line
2.17.0
PATCH v2 1/4 btrfs: compression: Add linux/sizes.h for compression.h
Since compression.h is using SZ_* macros, and if some user only includes compression.h without linux/sizes.h, it will cause compile error.
One example is lzo.c, if it uses BTRFS_MAX_COMPRESSED, it would cause compile error.
Fix it by adding linux/sizes.h in compression.h
--- fs/btrfs/compression.h | 1 + 1 file changed, 1 insertion(+)
fs/btrfs/compression.h +1 -0
@@ -6,6 +6,7 @@#ifndef BTRFS_COMPRESSION_H #define BTRFS_COMPRESSION_H +#include <linux/sizes.h> /* * We want to make sure that amount of RAM required to uncompress an extent is * reasonable, so we limit the total size in ram of a compressed extent to
Signature · 1 line
2.17.0
PATCH v2 2/4 btrfs: lzo: Add comment about the how btrfs records its lzo compressed data
In reply to Qu WenruoAlthough it's not that complex, but such comment could still save several minutes for newer reader/reviewer.
--- fs/btrfs/lzo.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+)
fs/btrfs/lzo.c +23 -0
@@ -17,6 +17,29 @@#define LZO_LEN 4 +/* +* Btrfs LZO compression format +* +* Regular LZO compressed data extent consists of: +* 1. Header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size (*includes* the header) of real compressed data. +* +* 2. Segment(s) +* Variable size. Includes one segment header, and then data payload. +* One regular LZO compressed extent can have one or more segments. +* +* 2.1 Segment header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size of the segment (*excludes* the header). +* +* 2.2 Data Payload +* Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE). +* +* While for inlined LZO compressed data extent, it doesn't have Header, just +* *ONE* Segment. +*/ +struct workspace {void *mem;void *buf;/* where decompressed data goes */
Signature · 1 line
2.17.0
Re: [PATCH v2 2/4] btrfs: lzo: Add comment about the how btrfs records its lzo compressed data
Quoted 27 lines · Qu Wenruo
Although it's not that complex, but such comment could still save several minutes for newer reader/reviewer.
Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/lzo.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+)fs/btrfs/lzo.c +11
-0@@ -17,6 +17,29 @@#define LZO_LEN 4 +/* +* Btrfs LZO compression format +* +* Regular LZO compressed data extent consists of: +* 1. Header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size (*includes* the header) of real compressed data. +* +* 2. Segment(s) +* Variable size. Includes one segment header, and then data payload. +* One regular LZO compressed extent can have one or more segments.
fs/btrfs/lzo.c line 40
Quoted 10 lines
fs/btrfs/lzo.c +10
-0+* +* 2.1 Segment header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size of the segment (*excludes* the header). +* +* 2.2 Data Payload +* Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE). +* +* While for inlined LZO compressed data extent, it doesn't have Header, just +* *ONE* Segment.
It does have header that has the same value as the 1st segment header so it's skipped.
There's also one catch in the format that if there's a less then 4 bytes left to the page size, the new segment starts on the new page.
Re: [PATCH v2 2/4] btrfs: lzo: Add comment about the how btrfs records its lzo compressed data
Quoted 33 lines · David Sterba
Quoted 32 lines · Qu Wenruo
Although it's not that complex, but such comment could still save several minutes for newer reader/reviewer.
Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/lzo.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+)fs/btrfs/lzo.c +16
-0@@ -17,6 +17,29 @@#define LZO_LEN 4 +/* +* Btrfs LZO compression format +* +* Regular LZO compressed data extent consists of: +* 1. Header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size (*includes* the header) of real compressed data. +* +* 2. Segment(s) +* Variable size. Includes one segment header, and then data payload. +* One regular LZO compressed extent can have one or more segments. +* +* 2.1 Segment header +* Fixed size. LZO_LEN (4) bytes long, LE32. +* Records the total size of the segment (*excludes* the header). +*
Quoted 8 lines
fs/btrfs/lzo.c line 40
Quoted 5 lines
fs/btrfs/lzo.c +5
-0+* 2.2 Data Payload +* Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE). +* +* While for inlined LZO compressed data extent, it doesn't have Header, just +* *ONE* Segment. It does have header that has the same value as the 1st segment header so it's skipped.
Indeed, I just missed the first "data_in += LZO_LEN;" line.
And in that case, the header should also be checked.
Quoted 3 lines
There's also one catch in the format that if there's a less then 4 bytes left to the page size, the new segment starts on the new page.
I'll also update the patch to reflect this.
Thanks,
Qu
Quoted 5 lines
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH v2 3/4 btrfs: lzo: Add header length check to avoid slab out of bounds access
In reply to Qu WenruoJames Harvey reported that some corrupted compressed extent data can lead to various kernel memory corruption.
Such corrupted extent data belongs to inode with NODATASUM flags, thus data csum won't help us detecting such bug.
If lucky enough, kasan could catch it like:
==================================================================
BUG: KASAN: slab-out-of-bounds in lzo_decompress_bio+0x384/0x7a0 [btrfs] Write of size 4096 at addr ffff8800606cb0f8 by task kworker/u16:0/2338 CPU: 3 PID: 2338 Comm: kworker/u16:0 Tainted: G O 4.17.0-rc5-custom+ #50 Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 0.0.0 02/06/2015 Workqueue: btrfs-endio btrfs_endio_helper [btrfs] Call Trace: dump_stack+0xc2/0x16b print_address_description+0x6a/0x270 kasan_report+0x260/0x380 memcpy+0x34/0x50 lzo_decompress_bio+0x384/0x7a0 [btrfs] end_compressed_bio_read+0x99f/0x10b0 [btrfs] bio_endio+0x32e/0x640 normal_work_helper+0x15a/0xea0 [btrfs] process_one_work+0x7e3/0x1470 worker_thread+0x1b0/0x1170 kthread+0x2db/0x390 ret_from_fork+0x22/0x40
...
==================================================================
The offending compressed data has the following info:
Header: length 32768 (Looks completely valid)
Segment 0 Header: length 3472882419 (Obvious out of bounds)
Then when handling segment 0, since it's over the current page, we need the compressed data to workspace, then such large size would trigger out-of-bounds memory access, screwing up the whole kernel.
Fix it by adding extra checks on header and segment headers to ensure we won't access out-of-bounds, and even checks the decompressed data won't be out-of-bounds.
--- fs/btrfs/lzo.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)
fs/btrfs/lzo.c +34 -1
@@ -281,6 +281,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)unsigned long working_bytes;size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );unsigned long in_offset;unsigned long in_page_bytes_left;unsigned long tot_in;
@@ -294,6 +295,18 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) data_in =kmap (pages_in[0 ]); tot_len =read_compress_length (data_in); +/* +* Compressed data header check. +* +* The real compressed size can't exceed extent length, and all pages +* should be used (a full pending page is not possible). +* If this happens it means the compressed extent is corrupted. +*/ +if (tot_len >min_t (size_t,BTRFS_MAX_COMPRESSED , srclen) || + tot_len < srclen -PAGE_SIZE ) { + ret = -EUCLEAN ; + goto done; + } tot_in =LZO_LEN ; in_offset =LZO_LEN ;
@@ -308,6 +321,17 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) in_offset +=LZO_LEN ; tot_in +=LZO_LEN ; +/* +* Segment header check. +* +* The segment length must not exceed max lzo compression +* size, nor the total compressed size +*/ +if (in_len > max_segment_len || tot_in + in_len > tot_len) { + ret = -EUCLEAN ; + goto done; + } + tot_in += in_len; working_bytes = in_len; may_late_unmap = need_unmap = false;
@@ -358,7 +382,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) } } - out_len =lzo1x_worst_compress (PAGE_SIZE ); + out_len = max_segment_len; ret =lzo1x_decompress_safe (buf, in_len, workspace->buf, &out_len);if (need_unmap)
@@ -368,6 +392,15 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) ret = -EIO ;break ; } +/* +* Decompressed data length check. +* The uncompressed data should not exceed uncompressed extent +* size. +*/ +if (tot_out + out_len > cb->len) { + ret = -EUCLEAN ; +break ; + } buf_start = tot_out; tot_out += out_len;
Signature · 1 line
2.17.0
Re: [PATCH v2 3/4] btrfs: lzo: Add header length check to avoid slab out of bounds access
Quoted 35 lines · Qu Wenruo
James Harvey reported that some corrupted compressed extent data can lead to various kernel memory corruption.
Such corrupted extent data belongs to inode with NODATASUM flags, thus data csum won't help us detecting such bug.
If lucky enough, kasan could catch it like:
==================================================================BUG: KASAN: slab-out-of-bounds in lzo_decompress_bio+0x384/0x7a0 [btrfs] Write of size 4096 at addr ffff8800606cb0f8 by task kworker/u16:0/2338 CPU: 3 PID: 2338 Comm: kworker/u16:0 Tainted: G O 4.17.0-rc5-custom+ #50 Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 0.0.0 02/06/2015 Workqueue: btrfs-endio btrfs_endio_helper [btrfs] Call Trace: dump_stack+0xc2/0x16b print_address_description+0x6a/0x270 kasan_report+0x260/0x380 memcpy+0x34/0x50 lzo_decompress_bio+0x384/0x7a0 [btrfs] end_compressed_bio_read+0x99f/0x10b0 [btrfs] bio_endio+0x32e/0x640 normal_work_helper+0x15a/0xea0 [btrfs] process_one_work+0x7e3/0x1470 worker_thread+0x1b0/0x1170 kthread+0x2db/0x390 ret_from_fork+0x22/0x40...
==================================================================The offending compressed data has the following info:
Header: length 32768 (Looks completely valid)
Segment 0 Header: length 3472882419 (Obvious out of bounds)
Quoted 7 lines
Then when handling segment 0, since it's over the current page, we need the compressed data to workspace, then such large size would trigger out-of-bounds memory access, screwing up the whole kernel.
Fix it by adding extra checks on header and segment headers to ensure we won't access out-of-bounds, and even checks the decompressed data won't be out-of-bounds.
Good, feel free to add more if you find them. The BUG_ON in lzo_decompress can be replaced by return -EUCLEAN and the total size can be compared with the segment size if they match too.
Quoted 11 lines
Reported-by James Harvey <[email protected]>Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/lzo.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)fs/btrfs/lzo.c +0
-0
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 284
Quoted 4 lines
fs/btrfs/lzo.c +1
-0@@ -281,6 +281,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)unsigned long working_bytes;size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );
The value is a compile-time constant, it does not need to be stored in a variable.
Quoted 6 lines
fs/btrfs/lzo.c +0
-0unsigned long in_offset;unsigned long in_page_bytes_left;unsigned long tot_in;@@ -294,6 +295,18 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) data_in =kmap (pages_in[0 ]);
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 306
Quoted 10 lines
fs/btrfs/lzo.c +9
-0tot_len =read_compress_length (data_in); +/* +* Compressed data header check. +* +* The real compressed size can't exceed extent length, and all pages +* should be used (a full pending page is not possible). +* If this happens it means the compressed extent is corrupted. +*/ +if (tot_len >min_t (size_t,BTRFS_MAX_COMPRESSED , srclen) || + tot_len < srclen -PAGE_SIZE ) {
All such conditions can be put into unlikely() as this is an error handling shortcut.
Quoted 56 lines
fs/btrfs/lzo.c +24
-1+ ret = -EUCLEAN ; + goto done; + } tot_in =LZO_LEN ; in_offset =LZO_LEN ;@@ -308,6 +321,17 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) in_offset +=LZO_LEN ; tot_in +=LZO_LEN ; +/* +* Segment header check. +* +* The segment length must not exceed max lzo compression +* size, nor the total compressed size +*/ +if (in_len > max_segment_len || tot_in + in_len > tot_len) { + ret = -EUCLEAN ; + goto done; + } + tot_in += in_len; working_bytes = in_len; may_late_unmap = need_unmap = false;@@ -358,7 +382,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) } } - out_len =lzo1x_worst_compress (PAGE_SIZE ); + out_len = max_segment_len; ret =lzo1x_decompress_safe (buf, in_len, workspace->buf, &out_len);if (need_unmap)@@ -368,6 +392,15 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) ret = -EIO ;break ; } +/* +* Decompressed data length check. +* The uncompressed data should not exceed uncompressed extent +* size. +*/ +if (tot_out + out_len > cb->len) { + ret = -EUCLEAN ; +break ; + } buf_start = tot_out; tot_out += out_len;Signature · 6 lines
2.17.0 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2 3/4] btrfs: lzo: Add header length check to avoid slab out of bounds access
Quoted 54 lines · David Sterba
Quoted 35 lines · Qu Wenruo
James Harvey reported that some corrupted compressed extent data can lead to various kernel memory corruption.
Such corrupted extent data belongs to inode with NODATASUM flags, thus data csum won't help us detecting such bug.
If lucky enough, kasan could catch it like:
==================================================================BUG: KASAN: slab-out-of-bounds in lzo_decompress_bio+0x384/0x7a0 [btrfs] Write of size 4096 at addr ffff8800606cb0f8 by task kworker/u16:0/2338 CPU: 3 PID: 2338 Comm: kworker/u16:0 Tainted: G O 4.17.0-rc5-custom+ #50 Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 0.0.0 02/06/2015 Workqueue: btrfs-endio btrfs_endio_helper [btrfs] Call Trace: dump_stack+0xc2/0x16b print_address_description+0x6a/0x270 kasan_report+0x260/0x380 memcpy+0x34/0x50 lzo_decompress_bio+0x384/0x7a0 [btrfs] end_compressed_bio_read+0x99f/0x10b0 [btrfs] bio_endio+0x32e/0x640 normal_work_helper+0x15a/0xea0 [btrfs] process_one_work+0x7e3/0x1470 worker_thread+0x1b0/0x1170 kthread+0x2db/0x390 ret_from_fork+0x22/0x40...
==================================================================The offending compressed data has the following info:
Header: length 32768 (Looks completely valid)
Segment 0 Header: length 3472882419 (Obvious out of bounds)Quoted 7 lines
Then when handling segment 0, since it's over the current page, we need the compressed data to workspace, then such large size would trigger out-of-bounds memory access, screwing up the whole kernel.
Fix it by adding extra checks on header and segment headers to ensure we won't access out-of-bounds, and even checks the decompressed data won't be out-of-bounds.
Good, feel free to add more if you find them. The
BUG_ONinlzo_decompresscan be replaced by return-EUCLEANand the total size can be compared with the segment size if they match too.Quoted 6 lines
Reported-by James Harvey <[email protected]>Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/lzo.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)
Quoted 12 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 284
Quoted 9 lines
fs/btrfs/lzo.c +1
-0@@ -281,6 +281,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)unsigned long working_bytes;size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );The value is a compile-time constant, it does not need to be stored in a variable.
Just to save some long lines, as it's used several times.
Quoted 6 lines
Quoted 6 lines
fs/btrfs/lzo.c +0
-0unsigned long in_offset;unsigned long in_page_bytes_left;unsigned long tot_in;@@ -294,6 +295,18 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
Quoted 14 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 306
Quoted 11 lines
fs/btrfs/lzo.c +9
-0data_in =kmap (pages_in[0 ]); tot_len =read_compress_length (data_in); +/* +* Compressed data header check. +* +* The real compressed size can't exceed extent length, and all pages +* should be used (a full pending page is not possible). +* If this happens it means the compressed extent is corrupted. +*/ +if (tot_len >min_t (size_t,BTRFS_MAX_COMPRESSED , srclen) || + tot_len < srclen -PAGE_SIZE ) {All such conditions can be put into
unlikely()as this is an error handling shortcut.
I'm OK to put it into unlikely().
I'll update this in next version.
Thanks,
Qu
Quoted 57 lines
Quoted 57 lines
fs/btrfs/lzo.c +24
-1+ ret = -EUCLEAN ; + goto done; + } tot_in =LZO_LEN ; in_offset =LZO_LEN ;@@ -308,6 +321,17 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) in_offset +=LZO_LEN ; tot_in +=LZO_LEN ; +/* +* Segment header check. +* +* The segment length must not exceed max lzo compression +* size, nor the total compressed size +*/ +if (in_len > max_segment_len || tot_in + in_len > tot_len) { + ret = -EUCLEAN ; + goto done; + } + tot_in += in_len; working_bytes = in_len; may_late_unmap = need_unmap = false;@@ -358,7 +382,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) } } - out_len =lzo1x_worst_compress (PAGE_SIZE ); + out_len = max_segment_len; ret =lzo1x_decompress_safe (buf, in_len, workspace->buf, &out_len);if (need_unmap)@@ -368,6 +392,15 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) ret = -EIO ;break ; } +/* +* Decompressed data length check. +* The uncompressed data should not exceed uncompressed extent +* size. +*/ +if (tot_out + out_len > cb->len) { + ret = -EUCLEAN ; +break ; + } buf_start = tot_out; tot_out += out_len;Signature · 6 lines
2.17.0 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2 3/4] btrfs: lzo: Add header length check to avoid slab out of bounds access
Quoted 11 lines · Qu Wenruo
Quoted 10 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 284
Quoted 7 lines
fs/btrfs/lzo.c +1
-0@@ -281,6 +281,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)unsigned long working_bytes;size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );The value is a compile-time constant, it does not need to be stored in a variable.
Quoted 1 line
Just to save some long lines, as it's used several times.
My concern is about the eventual stack consumption by the variable. I haven't measured that as the stack-bloat-script is now somehow broken so I'm basing this on my previous evaluations. The long term plan is to remove unnecessary variables or at least help the compiler to optimize them out, every few bytes help and we hope for the cumulative effect.
The replacement by local variable sort of does not need to be in this patch as it's not used for the header length check itself.
Quoted 17 lines
Quoted 16 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 306
Quoted 13 lines
fs/btrfs/lzo.c +9
-0@@ -294,6 +295,18 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) data_in =kmap (pages_in[0 ]); tot_len =read_compress_length (data_in); +/* +* Compressed data header check. +* +* The real compressed size can't exceed extent length, and all pages +* should be used (a full pending page is not possible). +* If this happens it means the compressed extent is corrupted. +*/ +if (tot_len >min_t (size_t,BTRFS_MAX_COMPRESSED , srclen) || + tot_len < srclen -PAGE_SIZE ) {All such conditions can be put into
unlikely()as this is an error handling shortcut.
Quoted 3 lines
I'm OK to put it into
unlikely().I'll update this in next version.
I don't see the unlikely() in the most recent version but after some considerations, I don't think it's needed. I'd rather look at the final assembly if the compiler is smart enough to recognize the pattern.
Adding likely/unlikely without some proof is not welcome in general, though in this case it's the allowed "jump to error handling".
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH v2 3/4] btrfs: lzo: Add header length check to avoid slab out of bounds access
Quoted 83 lines · Qu Wenruo
Quoted 12 lines · David Sterba
Quoted 11 lines · Qu Wenruo
Quoted 10 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 284
Quoted 7 lines
fs/btrfs/lzo.c +1
-0@@ -281,6 +281,7 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)unsigned long working_bytes;size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );The value is a compile-time constant, it does not need to be stored in a variable.
Quoted 7 lines
Quoted 1 line
Just to save some long lines, as it's used several times.
My concern is about the eventual stack consumption by the variable. I haven't measured that as the stack-bloat-script is now somehow broken so I'm basing this on my previous evaluations. The long term plan is to remove unnecessary variables or at least help the compiler to optimize them out, every few bytes help and we hope for the cumulative effect.
I think for such constant value, compiler should be clear enough to avoid the usage of stack.
And in fact it indeed avoids the usage of stack memory, even without const prefix.
All operation related to @max_segment_len are using immediate number 4419. (Result is from gcc 8.1)
------lzo_decompress_bio:
1: call__fentry__pushq %r15 # movq %rdi, %r15 # ws, ws movq %rsi, %rdi # cb, cb pushq %r14 # pushq %r13 # pushq %r12 # pushq %rbp # pushq %rbx # addq $-128, %rsp #, # fs/btrfs//lzo.c:305: u64 disk_start = cb->start; movq 24(%rdi), %rcx # cb_63(D)->start, disk_start # fs/btrfs//lzo.c:283: { movq %rsi, 32(%rsp) # cb, %sfp movq %gs:40, %rax # MEM[(<address-space-2> long unsigned int *)40B], tmp197 movq %rax, 120(%rsp) # tmp197, D.32453 xorl %eax, %eax # tmp197 # fs/btrfs//lzo.c:288: size_t srclen = cb->compressed_len; movq 40(%rsi), %rax # cb_63(D)->compressed_len, srclen # fs/btrfs//lzo.c:304: struct page **pages_in = cb->compressed_pages; movq 8(%rsi), %rsi # cb_63(D)->compressed_pages, pages_in # fs/btrfs//lzo.c:305: u64 disk_start = cb->start; movq %rcx, 40(%rsp) # disk_start, %sfp # ./include/linux/mm.h:1098: return page_to_virt(page); movabsq $-131941395333120, %rcx #, tmp154 # fs/btrfs//lzo.c:289: unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE); leaq 4095(%rax), %rdx #, tmp147 # ./include/linux/mm.h:1098: return page_to_virt(page); movq (%rsi), %rbp # *pages_in_66, tmp148 # fs/btrfs//lzo.c:304: struct page **pages_in = cb->compressed_pages; movq %rsi, 88(%rsp) # pages_in, %sfp # fs/btrfs//lzo.c:317: if (tot_len > min_t(size_t, BTRFS_MAX_COMPRESSED, srclen) || movl $131072, %esi #, tmp156 # fs/btrfs//lzo.c:289: unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE); shrq $12, %rdx #, tmp147 movq %rdx, 80(%rsp) # tmp147, %sfp # fs/btrfs//lzo.c:306: struct bio *orig_bio = cb->orig_bio; movq 72(%rdi), %rdx # cb_63(D)->orig_bio, orig_bio movq %rdx, 24(%rsp) # orig_bio, %sfp # ./include/linux/mm.h:1098: return page_to_virt(page); movabsq $24189255811072, %rdx #, tmp149 addq %rdx, %rbp # tmp149, tmp148 sarq $6, %rbp #, tmp152 salq $12, %rbp #, tmp153 addq %rcx, %rbp # tmp154, data_in # fs/btrfs//lzo.c:317: if (tot_len > min_t(size_t, BTRFS_MAX_COMPRESSED, srclen) || cmpq $131072, %rax #, srclen
Quoted 4 lines
------
My question is, if this is a little overkilled for us human to do all the work which should be done by compiler.
It depends, if we know the value is a constant and want to give it a symbolic name, then it's ok to add the variable. That's IMO not an overkill but a good coding practice. If there's no const but there are no writes to the variable, the compiler can assume it's a constant and treat it like that. But this requires additional logic.
Quoted 24 lines
Quoted 24 lines
The replacement by local variable sort of does not need to be in this patch as it's not used for the header length check itself.
Quoted 20 lines
Quoted 16 lines
fs/btrfs/lzo.c static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) · line 306
Quoted 13 lines
fs/btrfs/lzo.c +9
-0@@ -294,6 +295,18 @@ static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) data_in =kmap (pages_in[0 ]); tot_len =read_compress_length (data_in); +/* +* Compressed data header check. +* +* The real compressed size can't exceed extent length, and all pages +* should be used (a full pending page is not possible). +* If this happens it means the compressed extent is corrupted. +*/ +if (tot_len >min_t (size_t,BTRFS_MAX_COMPRESSED , srclen) || + tot_len < srclen -PAGE_SIZE ) {All such conditions can be put into
unlikely()as this is an error handling shortcut.I'm OK to put it into
unlikely().I'll update this in next version.
Quoted 8 lines
Quoted 3 lines
I don't see the
unlikely()in the most recent version but after some considerations, I don't think it's needed. I'd rather look at the final assembly if the compiler is smart enough to recognize the pattern.With .s from gcc 8.1 attached.
Bothunlikely()added and withoutunlikely().There is some difference, however I can't really tell.
Typically the diff between the version shos that a part of the function is moved to the end so the unlikely code is not in the sequence of instructions.
Quoted 5 lines
Quoted 2 lines
Adding likely/unlikely without some proof is not welcome in general, though in this case it's the allowed "jump to error handling".
Forgot to mention that, IIRC years ago someone told me not to use likely/unlikely unless really needed.
And the jump to error handling code, when the condition cannot be predicted during compile time, is one such use. The statically predictable conditions are eg. NULL pointer checks.
Quoted 3 lines
And in my understanding, such "optimization" doesn't really make much sense since the branch prediction implemented by hardware would have larger impact.
I've asked about that some CPU people if this does have an impact and the answer is yes. The details are about instruction stream parsing and pipelining etc, but on that level, if the likely instruction is in the buffer it's less work compared to fetching unparsed instructions a few bytes later.
The compression code can be optimized more and split to hot and cold paths as this is in-memory processing and potentially called many times. Here the error handling is the cold path, and as it's catching possible but highly unlikely case, moving that out of the hot path is still worth doing.
PATCH v2 4/4 btrfs: lzo: Harden inline lzo compressed extent decompression
In reply to Qu WenruoUnlike regular lzo compressed extent, inline extent doesn't have Header and only has one Segment.
And further more, inlined extent always has csum in its leaf header, it's less possible to have corrupted data.
Anyway, still add extra segment header length check.
--- fs/btrfs/lzo.c | 5 +++++ 1 file changed, 5 insertions(+)
fs/btrfs/lzo.c +5 -0
@@ -425,6 +425,7 @@ static int lzo_decompress(struct list_head *ws, unsigned char *data_in, struct workspace *workspace = list_entry(ws, struct workspace, list);size_t in_len;size_t out_len; +size_t max_segment_len =lzo1x_worst_compress (PAGE_SIZE );int ret =0 ;char *kaddr;unsigned long bytes;
@@ -434,6 +435,10 @@ static int lzo_decompress(struct list_head *ws, unsigned char *data_in, data_in +=LZO_LEN ; in_len =read_compress_length (data_in); +if (in_len > max_segment_len) { + ret = -EUCLEAN ; + goto out; + } data_in +=LZO_LEN ; out_len =PAGE_SIZE ;
Signature · 1 line
2.17.0