Skip to contentSkip to conversation

pstore: Base compression input buffer size on estimated compressed size

PATCH In review Ard Biesheuvel 3 participants 5 messages Aug 30, 2023 – Aug 31, 2023 Pstore filesystem

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 pstore: Base compression input buffer size on estimated compressed size

Commit 1756ddea6916 ("pstore: Remove worst-case compression size logic") removed some clunky per-algorithm worst case size estimation routines on the basis that we can always store pstore records uncompressed, and these worst case estimations are about how much the size might inadvertently *increase* due to encapsulation overhead when the input cannot be compressed at all. So if compression results in a size increase, we just store the original data instead.

However, it seems that the the original code was misinterpreting these calculations as an estimation of how much uncompressed data might fit into a compressed buffer of a given size, and it was using the results to consume the input data in larger chunks than the pstore record size, relying on the compression to ensure that what ultimately gets stored fits into the available space.

One result of this, as observed and reported by Linus, is that upgrading to a newer kernel that includes the given commit may result in pstore decompression errors reported in the kernel log. This is due to the fact that the existing records may unexpectedly decompress to a size that is larger than the pstore record size.

Another potential problem caused by this change is that we may underutilize the fixed sized records on pstore backends such as ramoops. And on pstore backends with variable sized records such as EFI, we will end up creating many more entries than before to store the same amount of compressed data.

So let's fix both issues, by bringing back the typical case estimation of how much ASCII text captured from the dmesg log might fit into a pstore record of a given size after compression. The original implementation used the computation given below for zlib, and so simply taking 2x as a ballpark number seems appropriate here.

  switch (size) {
  /* buffer range for efivars */
  case 1000 ... 2000:
  	cmpr = 56;
  	break;
  case 2001 ... 3000:
  	cmpr = 54;
  	break;
  case 3001 ... 3999:
  	cmpr = 52;
  	break;
  /* buffer range for nvram, erst */
  case 4000 ... 10000:
  	cmpr = 45;
  	break;
  default:
  	cmpr = 60;
  	break;
  }

  return (size * 100) / cmpr;

While at it, rate limit the error message so we don't flood the log unnecessarily on systems that have accumulated a lot of pstore history.

Cc Linus Torvalds <[email protected]>
Cc Eric Biggers <[email protected]>
Cc Kees Cook <[email protected]>
Cc Herbert Xu <[email protected]>
---
 fs/pstore/platform.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/pstore/platform.c +23 -7
index 62356d542ef67f60..a866b70ea5933a1d 100644
@@ -98,7 +98,14 @@ MODULE_PARM_DESC(kmsg_bytes, "amount of kernel log to snapshot (in bytes)");
 
 static void *compress_workspace;
 
+/*
+ * Compression is only used for dmesg output, which consists of low-entropy
+ * ASCII text, and so we can assume a 2x compression factor is achievable.
+ */
+#define DMESG_COMP_FACTOR	2
+
 static char *big_oops_buf;
+static size_t max_uncompressed_size;
 
 void pstore_set_kmsg_bytes(int bytes)
 {
@@ -216,7 +223,7 @@ static void allocate_buf_for_compression(void)
 	 * uncompressed record size, since any record that would be expanded by
 	 * compression is just stored uncompressed.
 	 */
-	buf = kvzalloc(psinfo->bufsize, GFP_KERNEL);
+	buf = kvzalloc(DMESG_COMP_FACTOR * psinfo->bufsize, GFP_KERNEL);
 	if (!buf) {
 		pr_err("Failed %zu byte compression buffer allocation for: %s\n",
 		       psinfo->bufsize, compress);
@@ -233,6 +240,7 @@ static void allocate_buf_for_compression(void)
 
 	/* A non-NULL big_oops_buf indicates compression is available. */
 	big_oops_buf = buf;
+	max_uncompressed_size = DMESG_COMP_FACTOR * psinfo->bufsize;
 
 	pr_info("Using crash dump compression: %s\n", compress);
 }
@@ -246,6 +254,7 @@ static void free_buf_for_compression(void)
 
 	kvfree(big_oops_buf);
 	big_oops_buf = NULL;
+	max_uncompressed_size = 0;
 }
 
 void pstore_record_init(struct pstore_record *record,
@@ -305,7 +314,7 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 		record.buf = psinfo->buf;
 
 		dst = big_oops_buf ?: psinfo->buf;
-		dst_size = psinfo->bufsize;
+		dst_size = max_uncompressed_size ?: psinfo->bufsize;
 
 		/* Write dump header. */
 		header_size = snprintf(dst, dst_size, "%s#%d Part%u\n", why,
@@ -326,8 +335,15 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 				record.compressed = true;
 				record.size = zipped_len;
 			} else {
-				record.size = header_size + dump_size;
-				memcpy(psinfo->buf, dst, record.size);
+				/*
+				 * Compression failed, so the buffer is most
+				 * likely filled with binary data that does not
+				 * compress as well as ASCII text. Copy as much
+				 * of the uncompressed data as possible into
+				 * the pstore record, and discard the rest.
+				 */
+				record.size = psinfo->bufsize;
+				memcpy(psinfo->buf, dst, psinfo->bufsize);
 			}
 		} else {
 			record.size = header_size + dump_size;
@@ -583,7 +599,7 @@ static void decompress_record(struct pstore_record *record,
 	}
 
 	/* Allocate enough space to hold max decompression and ECC. */
-	workspace = kvzalloc(psinfo->bufsize + record->ecc_notice_size,
+	workspace = kvzalloc(max_uncompressed_size + record->ecc_notice_size,
 			     GFP_KERNEL);
 	if (!workspace)
 		return;
@@ -591,11 +607,11 @@ static void decompress_record(struct pstore_record *record,
 	zstream->next_in	= record->buf;
 	zstream->avail_in	= record->size;
 	zstream->next_out	= workspace;
-	zstream->avail_out	= psinfo->bufsize;
+	zstream->avail_out	= max_uncompressed_size;
 
 	ret = zlib_inflate(zstream, Z_FINISH);
 	if (ret != Z_STREAM_END) {
-		pr_err("zlib_inflate() failed, ret = %d!\n", ret);
+		pr_err_ratelimited("zlib_inflate() failed, ret = %d!\n", ret);
 		kvfree(workspace);
 		return;
 	}
Signature · 1 line
2.39.2
#1 lore raw
Quoted 7 lines · Ard Biesheuvel

Commit 1756ddea6916 ("pstore: Remove worst-case compression size logic") removed some clunky per-algorithm worst case size estimation routines on the basis that we can always store pstore records uncompressed, and these worst case estimations are about how much the size might inadvertently *increase* due to encapsulation overhead when the input cannot be compressed at all. So if compression results in a size increase, we just store the original data instead.

Does the Z_FINISH vs Z_SYNC_FLUSH thing need to be fixed as well, or does that become a non-issue with this change?

Quoted 118 lines

However, it seems that the the original code was misinterpreting these calculations as an estimation of how much uncompressed data might fit into a compressed buffer of a given size, and it was using the results to consume the input data in larger chunks than the pstore record size, relying on the compression to ensure that what ultimately gets stored fits into the available space.

One result of this, as observed and reported by Linus, is that upgrading to a newer kernel that includes the given commit may result in pstore decompression errors reported in the kernel log. This is due to the fact that the existing records may unexpectedly decompress to a size that is larger than the pstore record size.

Another potential problem caused by this change is that we may underutilize the fixed sized records on pstore backends such as ramoops. And on pstore backends with variable sized records such as EFI, we will end up creating many more entries than before to store the same amount of compressed data.

So let's fix both issues, by bringing back the typical case estimation of how much ASCII text captured from the dmesg log might fit into a pstore record of a given size after compression. The original implementation used the computation given below for zlib, and so simply taking 2x as a ballpark number seems appropriate here.

  switch (size) {
  /* buffer range for efivars */
  case 1000 ... 2000:
  	cmpr = 56;
  	break;
  case 2001 ... 3000:
  	cmpr = 54;
  	break;
  case 3001 ... 3999:
  	cmpr = 52;
  	break;
  /* buffer range for nvram, erst */
  case 4000 ... 10000:
  	cmpr = 45;
  	break;
  default:
  	cmpr = 60;
  	break;
  }

  return (size * 100) / cmpr;

While at it, rate limit the error message so we don't flood the log unnecessarily on systems that have accumulated a lot of pstore history.

Cc Linus Torvalds <[email protected]>
Cc Eric Biggers <[email protected]>
Cc Kees Cook <[email protected]>
Cc Herbert Xu <[email protected]>
---
 fs/pstore/platform.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/pstore/platform.c +11 -3
index 62356d542ef67f60..a866b70ea5933a1d 100644
@@ -98,7 +98,14 @@ MODULE_PARM_DESC(kmsg_bytes, "amount of kernel log to snapshot (in bytes)");
 
 static void *compress_workspace;
 
+/*
+ * Compression is only used for dmesg output, which consists of low-entropy
+ * ASCII text, and so we can assume a 2x compression factor is achievable.
+ */
+#define DMESG_COMP_FACTOR	2
+
 static char *big_oops_buf;
+static size_t max_uncompressed_size;
 
 void pstore_set_kmsg_bytes(int bytes)
 {
@@ -216,7 +223,7 @@ static void allocate_buf_for_compression(void)
 	 * uncompressed record size, since any record that would be expanded by
 	 * compression is just stored uncompressed.
 	 */
-	buf = kvzalloc(psinfo->bufsize, GFP_KERNEL);
+	buf = kvzalloc(DMESG_COMP_FACTOR * psinfo->bufsize, GFP_KERNEL);
 	if (!buf) {
 		pr_err("Failed %zu byte compression buffer allocation for: %s\n",
 		       psinfo->bufsize, compress);
@@ -233,6 +240,7 @@ static void allocate_buf_for_compression(void)
 
 	/* A non-NULL big_oops_buf indicates compression is available. */
 	big_oops_buf = buf;
+	max_uncompressed_size = DMESG_COMP_FACTOR * psinfo->bufsize;
 
 	pr_info("Using crash dump compression: %s\n", compress);
 }
@@ -246,6 +254,7 @@ static void free_buf_for_compression(void)
 
 	kvfree(big_oops_buf);
 	big_oops_buf = NULL;
+	max_uncompressed_size = 0;
 }
 
 void pstore_record_init(struct pstore_record *record,
@@ -305,7 +314,7 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 		record.buf = psinfo->buf;
 
 		dst = big_oops_buf ?: psinfo->buf;
-		dst_size = psinfo->bufsize;
+		dst_size = max_uncompressed_size ?: psinfo->bufsize;
 
 		/* Write dump header. */
 		header_size = snprintf(dst, dst_size, "%s#%d Part%u\n", why,
@@ -326,8 +335,15 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 				record.compressed = true;
 				record.size = zipped_len;
 			} else {
-				record.size = header_size + dump_size;

fs/pstore/platform.c static void pstore_dump(struct kmsg_dumper *dumper, · line 346

Quoted 10 lines
fs/pstore/platform.c +9 -1
-				memcpy(psinfo->buf, dst, record.size);
+				/*
+				 * Compression failed, so the buffer is most
+				 * likely filled with binary data that does not
+				 * compress as well as ASCII text. Copy as much
+				 * of the uncompressed data as possible into
+				 * the pstore record, and discard the rest.
+				 */
+				record.size = psinfo->bufsize;
+				memcpy(psinfo->buf, dst, psinfo->bufsize);

I don't think this is "friendly" enough. :P

In the compression failure case, we've got a larger dst_size (and dump_size, but technically it might not be true if something else went wrong) than psinfo->bufsize, so we want to take the trailing bytes (i.e. panic details are more likely at the end). And we should keep the header, which is already present in "dst". I think we need to do something like this:

	size_t buf_size_available = psinfo->bufsize - header_size;
	size_t dump_size_wanted = min(dump_size, buf_size_available);

	record.size = header_size + dump_size_wanted;
	memcpy(psinfo->buf, dst, header_size);
	memcpy(psinfo->buf + header_size,
	       dst + header_size + (dump_size - dump_size_wanted),
	       dump_size_wanted);

My eyes, my eyes.

Quoted 29 lines
fs/pstore/platform.c +3 -3
 			}
 		} else {
 			record.size = header_size + dump_size;
@@ -583,7 +599,7 @@ static void decompress_record(struct pstore_record *record,
 	}
 
 	/* Allocate enough space to hold max decompression and ECC. */
-	workspace = kvzalloc(psinfo->bufsize + record->ecc_notice_size,
+	workspace = kvzalloc(max_uncompressed_size + record->ecc_notice_size,
 			     GFP_KERNEL);
 	if (!workspace)
 		return;
@@ -591,11 +607,11 @@ static void decompress_record(struct pstore_record *record,
 	zstream->next_in	= record->buf;
 	zstream->avail_in	= record->size;
 	zstream->next_out	= workspace;
-	zstream->avail_out	= psinfo->bufsize;
+	zstream->avail_out	= max_uncompressed_size;
 
 	ret = zlib_inflate(zstream, Z_FINISH);
 	if (ret != Z_STREAM_END) {
-		pr_err("zlib_inflate() failed, ret = %d!\n", ret);
+		pr_err_ratelimited("zlib_inflate() failed, ret = %d!\n", ret);
 		kvfree(workspace);
 		return;
 	}
Signature · 1 line
2.39.2

Otherwise, yes, this should do nicely. :)

Signature · 1 line
Kees Cook
#2 lore raw
Quoted 11 lines · Kees Cook
Quoted 7 lines · Ard Biesheuvel

Commit 1756ddea6916 ("pstore: Remove worst-case compression size logic") removed some clunky per-algorithm worst case size estimation routines on the basis that we can always store pstore records uncompressed, and these worst case estimations are about how much the size might inadvertently *increase* due to encapsulation overhead when the input cannot be compressed at all. So if compression results in a size increase, we just store the original data instead.

Does the Z_FINISH vs Z_SYNC_FLUSH thing need to be fixed as well, or does that become a non-issue with this change?

I haven't seen any real evidence that that issue actually exists.

Quoted 44 lines
Quoted 15 lines

void pstore_record_init(struct pstore_record *record,

fs/pstore/platform.c +1 -2
@@ -305,7 +314,7 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 		record.buf = psinfo->buf;
 
 		dst = big_oops_buf ?: psinfo->buf;
-		dst_size = psinfo->bufsize;
+		dst_size = max_uncompressed_size ?: psinfo->bufsize;
 
 		/* Write dump header. */
 		header_size = snprintf(dst, dst_size, "%s#%d Part%u\n", why,
@@ -326,8 +335,15 @@ static void pstore_dump(struct kmsg_dumper *dumper,
 				record.compressed = true;
 				record.size = zipped_len;
 			} else {
-				record.size = header_size + dump_size;

fs/pstore/platform.c static void pstore_dump(struct kmsg_dumper *dumper, · line 346

Quoted 10 lines
fs/pstore/platform.c +9 -1
-				memcpy(psinfo->buf, dst, record.size);
+				/*
+				 * Compression failed, so the buffer is most
+				 * likely filled with binary data that does not
+				 * compress as well as ASCII text. Copy as much
+				 * of the uncompressed data as possible into
+				 * the pstore record, and discard the rest.
+				 */
+				record.size = psinfo->bufsize;
+				memcpy(psinfo->buf, dst, psinfo->bufsize);

I don't think this is "friendly" enough. :P

In the compression failure case, we've got a larger dst_size (and dump_size, but technically it might not be true if something else went wrong) than psinfo->bufsize, so we want to take the trailing bytes (i.e. panic details are more likely at the end). And we should keep the header, which is already present in "dst". I think we need to do something like this:

	size_t buf_size_available = psinfo->bufsize - header_size;
	size_t dump_size_wanted = min(dump_size, buf_size_available);

	record.size = header_size + dump_size_wanted;
	memcpy(psinfo->buf, dst, header_size);
	memcpy(psinfo->buf + header_size,
	       dst + header_size + (dump_size - dump_size_wanted),
	       dump_size_wanted);
Quoted 2 lines

My eyes, my eyes.

How hard would it be to write two uncompressed records when compression fails to achieve the targeted 50% ratio?

- Eric

#3 lore raw
Quoted 11 lines · Eric Biggers
Quoted 9 lines · Kees Cook
Quoted 7 lines · Ard Biesheuvel

Commit 1756ddea6916 ("pstore: Remove worst-case compression size logic") removed some clunky per-algorithm worst case size estimation routines on the basis that we can always store pstore records uncompressed, and these worst case estimations are about how much the size might inadvertently *increase* due to encapsulation overhead when the input cannot be compressed at all. So if compression results in a size increase, we just store the original data instead.

Quoted 5 lines
Quoted 2 lines

Does the Z_FINISH vs Z_SYNC_FLUSH thing need to be fixed as well, or does that become a non-issue with this change?

I haven't seen any real evidence that that issue actually exists.

Indeed. The workaround in crypto/deflate.c was added in 2003 by James Morris, and the zlib fork was rebased onto a newer upstream at least once since then.

Quoted 44 lines
Quoted 44 lines
Quoted 15 lines

void pstore_record_init(struct pstore_record *record,

fs/pstore/platform.c +1 -2
@@ -305,7 +314,7 @@ static void pstore_dump(struct kmsg_dumper *dumper,
            record.buf = psinfo->buf;
 
            dst = big_oops_buf ?: psinfo->buf;
-           dst_size = psinfo->bufsize;
+           dst_size = max_uncompressed_size ?: psinfo->bufsize;
 
            /* Write dump header. */
            header_size = snprintf(dst, dst_size, "%s#%d Part%u\n", why,
@@ -326,8 +335,15 @@ static void pstore_dump(struct kmsg_dumper *dumper,
                            record.compressed = true;
                            record.size = zipped_len;
                    } else {
-                           record.size = header_size + dump_size;

fs/pstore/platform.c static void pstore_dump(struct kmsg_dumper *dumper, · line 346

Quoted 10 lines
fs/pstore/platform.c +9 -1
-                           memcpy(psinfo->buf, dst, record.size);
+                           /*
+                            * Compression failed, so the buffer is most
+                            * likely filled with binary data that does not
+                            * compress as well as ASCII text. Copy as much
+                            * of the uncompressed data as possible into
+                            * the pstore record, and discard the rest.
+                            */
+                           record.size = psinfo->bufsize;
+                           memcpy(psinfo->buf, dst, psinfo->bufsize);

I don't think this is "friendly" enough. :P

In the compression failure case, we've got a larger dst_size (and dump_size, but technically it might not be true if something else went wrong) than psinfo->bufsize, so we want to take the trailing bytes (i.e. panic details are more likely at the end). And we should keep the header, which is already present in "dst". I think we need to do something like this:

      size_t buf_size_available = psinfo->bufsize - header_size;
      size_t dump_size_wanted = min(dump_size, buf_size_available);

      record.size = header_size + dump_size_wanted;
      memcpy(psinfo->buf, dst, header_size);
      memcpy(psinfo->buf + header_size,
             dst + header_size + (dump_size - dump_size_wanted),
             dump_size_wanted);
Quoted 6 lines
Quoted 2 lines

My eyes, my eyes.

How hard would it be to write two uncompressed records when compression fails to achieve the targeted 50% ratio?

It wouldn't be that hard, and this crossed my mind as well.

However, we should ask ourselves when this is ever going to happen, and what the implications are for those records. The reason we want to capture the dmesg output is because it contains human readable ASCII text that explains what happened right before the system crashed.

The zlib library code uses pre-allocated buffers and so the most likely reason for failure is that the 2x estimation does not hold for the buffer in question. It is highly unlikely that that buffer contains ASCII text or anything resembling it in that case, and so it is most probably garbage that happens to compress really poorly. Do we really need to capture all of that? And if we don't, does it really matter whether the we capture the first bit or the last bit?

#4 lore raw
In reply to Ard Biesheuvel
Quoted 19 lines · Ard Biesheuvel

So let's fix both issues, by bringing back the typical case estimation of how much ASCII text captured from the dmesg log might fit into a pstore record of a given size after compression. The original implementation used the computation given below for zlib, and so simply taking 2x as a ballpark number seems appropriate here.

  switch (size) {
  /* buffer range for efivars */
  case 1000 ... 2000:
  	cmpr = 56;
  	break;
  case 2001 ... 3000:
  	cmpr = 54;
  	break;
  case 3001 ... 3999:
  	cmpr = 52;
  	break;
  /* buffer range for nvram, erst */
  case 4000 ... 10000:
Quoted 8 lines
  	cmpr = 45;
  	break;
  default:
  	cmpr = 60;
  	break;
  }

  return (size * 100) / cmpr;

I remained suspicious of this since the old worst-case was 60%, not 50%... In testing with some instrumentation I was able to find compression failures (see the "-22" results in the middle):

pstore: backend max size:1024 dump size:2034 zipped size:800
pstore: backend max size:1024 dump size:1943 zipped size:714
pstore: backend max size:1024 dump size:2008 zipped size:739
pstore: backend max size:1024 dump size:2024 zipped size:722
pstore: backend max size:1024 dump size:2017 zipped size:926
pstore: backend max size:1024 dump size:2046 zipped size:-22
pstore: backend max size:1024 dump size:2046 zipped size:-22
pstore: backend max size:1024 dump size:2007 zipped size:890
pstore: backend max size:1024 dump size:2035 zipped size:830
pstore: backend max size:1024 dump size:2012 zipped size:844
pstore: backend max size:1024 dump size:1978 zipped size:823
pstore: backend max size:1024 dump size:2013 zipped size:543
pstore: backend max size:1024 dump size:2000 zipped size:820

So, I altered the patch slightly to use the 60% worst-case (i.e. an underestimate), and that did the trick (you can see the smaller "dump size" output from the kmsg dumper):

pstore: backend max size:1024 dump size:1590 zipped size:553
pstore: backend max size:1024 dump size:1534 zipped size:792
pstore: backend max size:1024 dump size:1647 zipped size:414
pstore: backend max size:1024 dump size:1641 zipped size:599
pstore: backend max size:1024 dump size:1670 zipped size:643
pstore: backend max size:1024 dump size:1692 zipped size:684
pstore: backend max size:1024 dump size:1697 zipped size:934
pstore: backend max size:1024 dump size:1696 zipped size:870
pstore: backend max size:1024 dump size:1677 zipped size:791
pstore: backend max size:1024 dump size:1683 zipped size:772
pstore: backend max size:1024 dump size:1677 zipped size:742
pstore: backend max size:1024 dump size:1704 zipped size:714
pstore: backend max size:1024 dump size:1683 zipped size:715
pstore: backend max size:1024 dump size:1693 zipped size:479
pstore: backend max size:1024 dump size:1667 zipped size:487
pstore: backend max size:1024 dump size:1639 zipped size:760

However, we still need a different _decompression_ size, as we want to over-estimate that buffer size. I just used 3x which is going always be enough.

I'll send a v2 to see what you think...

Signature · 1 line
Kees Cook