[PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[David Laight]

Fastpath the normal case of single byte output that fits in the buffer.
Output byte groups (byteswapped on little-endian) without calling snprintf().
Remove the restriction that rowsize must be 16 or 32.
Remove the restriction that groupsize must be 8 or less.
If groupsize isn't a power of 2 or doesn't divide into both len and
  rowsize it is set to 1 (otherwise byteswapping is hard).
Change the types of the rowsize and groupsize parameters to be unsigned types.

Tested in a userspace harness, code size (x86-64) halved to 723 bytes.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 include/linux/printk.h |   6 +-
 lib/hexdump.c          | 165 ++++++++++++++++++++---------------------
 2 files changed, 85 insertions(+), 86 deletions(-)

diff --git a/include/linux/printk.h b/include/linux/printk.h
index 4217a9f412b2..49e67f63277e 100644
--- a/include/linux/printk.h
+++ b/include/linux/printk.h
@@ -752,9 +752,9 @@ enum {
 	DUMP_PREFIX_ADDRESS,
 	DUMP_PREFIX_OFFSET
 };
-extern int hex_dump_to_buffer(const void *buf, size_t len, int rowsize,
-			      int groupsize, char *linebuf, size_t linebuflen,
-			      bool ascii);
+extern size_t hex_dump_to_buffer(const void *buf, size_t len, size_t rowsize,
+			      size_t groupsize, char *linebuf,
+			      size_t linebuflen, bool ascii);
 #ifdef CONFIG_PRINTK
 extern void print_hex_dump(const char *level, const char *prefix_str,
 			   int prefix_type, int rowsize, int groupsize,
diff --git a/lib/hexdump.c b/lib/hexdump.c
index c3db7c3a7643..da40ae217c41 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -98,13 +98,16 @@ EXPORT_SYMBOL(bin2hex);
  * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory
  * @buf: data blob to dump
  * @len: number of bytes in the @buf
- * @rowsize: number of bytes to print per line; must be 16 or 32
- * @groupsize: number of bytes to print at a time (1, 2, 4, 8; default = 1)
+ * @rowsize: number of bytes to print per line
+ * @groupsize: number of bytes to print at a time
  * @linebuf: where to put the converted data
  * @linebuflen: total size of @linebuf, including space for terminating NUL
  * @ascii: include ASCII after the hex output
  *
- * hex_dump_to_buffer() works on one "line" of output at a time, i.e.,
+ * If @groupsize isn't a power of 2 that divides into both @len and @rowsize
+ * the it is set to 1.
+ *
+ * hex_dump_to_buffer() works on one "line" of output at a time, e.g.,
  * 16 or 32 bytes of input data converted to hex + ASCII output.
  *
  * Given a buffer of u8 data, hex_dump_to_buffer() converts the input data
@@ -124,105 +127,101 @@ EXPORT_SYMBOL(bin2hex);
  * (excluding the terminating NUL) which would have been written to the final
  * string if enough space had been available.
  */
-int hex_dump_to_buffer(const void *buf, size_t len, int rowsize, int groupsize,
-		       char *linebuf, size_t linebuflen, bool ascii)
+size_t hex_dump_to_buffer(const void *buf, size_t len, size_t rowsize,
+		       size_t groupsize, char *linebuf, size_t linebuflen,
+		       bool ascii)
 {
+	char *dst_end = linebuf + linebuflen;
+	size_t out_len, pad_len;
+	char *dst = linebuf;
 	const u8 *ptr = buf;
-	int ngroups;
+	unsigned int j;
 	u8 ch;
-	int j, lx = 0;
-	int ascii_column;
-	int ret;
 
-	if (rowsize != 16 && rowsize != 32)
-		rowsize = 16;
+	if (!len) {
+		if (linebuflen)
+			linebuf[0] = 0;
+		return 0;
+	}
 
-	if (len > rowsize)		/* limit to one line at a time */
-		len = rowsize;
-	if (!is_power_of_2(groupsize) || groupsize > 8)
-		groupsize = 1;
-	if ((len % groupsize) != 0)	/* no mixed size output */
-		groupsize = 1;
+	if (len > rowsize) {
+		if (rowsize == 0)
+			rowsize = 16;
+		if (len > rowsize)
+			len = rowsize;
+	}
 
-	ngroups = len / groupsize;
-	ascii_column = rowsize * 2 + rowsize / groupsize + 1;
+	if ((groupsize & (groupsize - 1)) || (rowsize & (groupsize - 1)) ||
+	    (len & (groupsize - 1)))
+		groupsize = 1;
 
-	if (!linebuflen)
-		goto overflow1;
+	if (groupsize == 1 && len * 3 <= linebuflen) {
+		for (j = 0; j < len; j++, dst += 3) {
+			ch = ptr[j];
+			dst[0] = hex_asc_hi(ch);
+			dst[1] = hex_asc_lo(ch);
+			dst[2] = ' ';
+		}
 
-	if (!len)
-		goto nil;
+		pad_len = (rowsize - len) * 3;
+	} else {
+		unsigned int mask = groupsize - 1;
+		unsigned int byteswap;
 
-	if (groupsize == 8) {
-		const u64 *ptr8 = buf;
+		byteswap = IS_ENABLED(CONFIG_CPU_BIG_ENDIAN) ? 0 : mask;
 
-		for (j = 0; j < ngroups; j++) {
-			ret = snprintf(linebuf + lx, linebuflen - lx,
-				       "%s%16.16llx", j ? " " : "",
-				       get_unaligned(ptr8 + j));
-			if (ret >= linebuflen - lx)
-				goto overflow1;
-			lx += ret;
-		}
-	} else if (groupsize == 4) {
-		const u32 *ptr4 = buf;
+		for (j = 0; j < len; j++) {
+			if (dst + 2 > dst_end)
+				goto hex_truncated;
+			ch = ptr[j ^ byteswap];
+			dst[0] = hex_asc_hi(ch);
+			dst[1] = hex_asc_lo(ch);
+			dst += 2;
 
-		for (j = 0; j < ngroups; j++) {
-			ret = snprintf(linebuf + lx, linebuflen - lx,
-				       "%s%8.8x", j ? " " : "",
-				       get_unaligned(ptr4 + j));
-			if (ret >= linebuflen - lx)
-				goto overflow1;
-			lx += ret;
+			if ((j & mask) != mask)
+				continue;
+			if (dst >= dst_end)
+				goto hex_truncated;
+			*dst++ = ' ';
 		}
-	} else if (groupsize == 2) {
-		const u16 *ptr2 = buf;
 
-		for (j = 0; j < ngroups; j++) {
-			ret = snprintf(linebuf + lx, linebuflen - lx,
-				       "%s%4.4x", j ? " " : "",
-				       get_unaligned(ptr2 + j));
-			if (ret >= linebuflen - lx)
-				goto overflow1;
-			lx += ret;
-		}
-	} else {
-		for (j = 0; j < len; j++) {
-			if (linebuflen < lx + 2)
-				goto overflow2;
-			ch = ptr[j];
-			linebuf[lx++] = hex_asc_hi(ch);
-			if (linebuflen < lx + 2)
-				goto overflow2;
-			linebuf[lx++] = hex_asc_lo(ch);
-			if (linebuflen < lx + 2)
-				goto overflow2;
-			linebuf[lx++] = ' ';
-		}
-		if (j)
-			lx--;
+		pad_len = rowsize - len;
+		pad_len = pad_len * 2 + pad_len / groupsize;
 	}
-	if (!ascii)
-		goto nil;
+	dst--;
+	out_len = dst - linebuf;
 
-	while (lx < ascii_column) {
-		if (linebuflen < lx + 2)
-			goto overflow2;
-		linebuf[lx++] = ' ';
+	if (!ascii) {
+		*dst = 0;
+		return out_len;
 	}
+
+	pad_len += 2;
+	out_len += pad_len + len;
+	if (dst + pad_len >= dst_end)
+		pad_len = dst_end - dst - 1;
+	while (pad_len--)
+		*dst++ = ' ';
+
+	if (dst + len >= dst_end)
+		len = dst_end - dst - 1;
+
 	for (j = 0; j < len; j++) {
-		if (linebuflen < lx + 2)
-			goto overflow2;
 		ch = ptr[j];
-		linebuf[lx++] = (isascii(ch) && isprint(ch)) ? ch : '.';
+		*dst++ = ch >= ' ' && ch < 0x7f ? ch : '.';
 	}
-nil:
-	linebuf[lx] = '\0';
-	return lx;
-overflow2:
-	linebuf[lx++] = '\0';
-overflow1:
-	return ascii ? ascii_column + len : (groupsize * 2 + 1) * ngroups - 1;
+	*dst = 0;
+
+	return out_len;
+
+hex_truncated:
+	if (dst_end != linebuf)
+		dst_end[-1] = 0;
+
+	out_len = ascii ? rowsize : len;
+	out_len = out_len * 2 + out_len / groupsize;
+	out_len += ascii ? 1 + len : -1;
+	return out_len;
 }
 EXPORT_SYMBOL(hex_dump_to_buffer);
 
-- 
2.39.5

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[Andy Shevchenko]

On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:
> Fastpath the normal case of single byte output that fits in the buffer.
> Output byte groups (byteswapped on little-endian) without calling snprintf().
> Remove the restriction that rowsize must be 16 or 32.
> Remove the restriction that groupsize must be 8 or less.
> If groupsize isn't a power of 2 or doesn't divide into both len and
>   rowsize it is set to 1 (otherwise byteswapping is hard).
> Change the types of the rowsize and groupsize parameters to be unsigned types.

> Tested in a userspace harness, code size (x86-64) halved to 723 bytes.

Does it imply running the respective test cases we have?
Do you need to add more test cases? I believe so.
Without test cases added it's a no go.

> +extern size_t hex_dump_to_buffer(const void *buf, size_t len, size_t rowsize,
> +			      size_t groupsize, char *linebuf,
> +			      size_t linebuflen, bool ascii);

Looking at another thread where upper layer function wants to have unsigned
long flags instead of bool ascii, I would also do the new API, that takes flags
and leave the old one as a simple wrapper with all restrictions being applied.

And again, provide it together with a bunch of test cases.

...

> +			dst[0] = hex_asc_hi(ch);
> +			dst[1] = hex_asc_lo(ch);

We have hex_pack_byte() or so

...

> +			ch = ptr[j ^ byteswap];
> +			dst[0] = hex_asc_hi(ch);
> +			dst[1] = hex_asc_lo(ch);
> +			dst += 2;

Ditto.

...

> -		linebuf[lx++] = (isascii(ch) && isprint(ch)) ? ch : '.';
> +		*dst++ = ch >= ' ' && ch < 0x7f ? ch : '.';

Please also add a test case for this to make sure it has no changes.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[David Laight]

On Sun, 16 Feb 2025 22:47:49 +0200
Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote:

> On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:
> > Fastpath the normal case of single byte output that fits in the buffer.
> > Output byte groups (byteswapped on little-endian) without calling snprintf().
> > Remove the restriction that rowsize must be 16 or 32.
> > Remove the restriction that groupsize must be 8 or less.
> > If groupsize isn't a power of 2 or doesn't divide into both len and
> >   rowsize it is set to 1 (otherwise byteswapping is hard).
> > Change the types of the rowsize and groupsize parameters to be unsigned types.  
> 
> > Tested in a userspace harness, code size (x86-64) halved to 723 bytes.  
> 
> Does it imply running the respective test cases we have?
> Do you need to add more test cases? I believe so.
> Without test cases added it's a no go.
> 
> > +extern size_t hex_dump_to_buffer(const void *buf, size_t len, size_t rowsize,
> > +			      size_t groupsize, char *linebuf,
> > +			      size_t linebuflen, bool ascii);  
> 
> Looking at another thread where upper layer function wants to have unsigned
> long flags instead of bool ascii, I would also do the new API, that takes flags
> and leave the old one as a simple wrapper with all restrictions being applied.

I can't imagine any code relying on the rowsize being converted to 16.
And (elsewhere) I've definitely needed to do hexdumps with strange numbers
of bytes/line.

> 
> And again, provide it together with a bunch of test cases.
> 
> ...
> 
> > +			dst[0] = hex_asc_hi(ch);
> > +			dst[1] = hex_asc_lo(ch);  
> 
> We have hex_pack_byte() or so

At least some versions of gcc have generated better code if you don't
use *ptr++ but do the increment afterwards.
It is also what the old version used.
Not to mention being another wrapper you need to look up to work out
what the code is doing.

..
> ...
> 
> > -		linebuf[lx++] = (isascii(ch) && isprint(ch)) ? ch : '.';
> > +		*dst++ = ch >= ' ' && ch < 0x7f ? ch : '.';  
> 
> Please also add a test case for this to make sure it has no changes.

Well isascii() usually checks for the 0x80 bit being clear and isprint()
rejects control characters and 'del' (0x7f).
I'm not sure what isascii() does for EBCDIC type charsets - but I don't
expect Linux runs on any of those so who cares.
Oh, and isprint() seems to be based on a memory lookup in an _ctype[] array.
Very 1970s.

	David

> 

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[Andy Shevchenko]

On Sun, Feb 16, 2025 at 10:37:15PM +0000, David Laight wrote:
> On Sun, 16 Feb 2025 22:47:49 +0200
> Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote:
> > On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:

...

> > > +extern size_t hex_dump_to_buffer(const void *buf, size_t len, size_t rowsize,
> > > +			      size_t groupsize, char *linebuf,
> > > +			      size_t linebuflen, bool ascii);  
> > 
> > Looking at another thread where upper layer function wants to have unsigned
> > long flags instead of bool ascii, I would also do the new API, that takes flags
> > and leave the old one as a simple wrapper with all restrictions being applied.
> 
> I can't imagine any code relying on the rowsize being converted to 16.
> And (elsewhere) I've definitely needed to do hexdumps with strange numbers
> of bytes/line.

I didn't get how this is related to my comment.

...

> > > +			dst[0] = hex_asc_hi(ch);
> > > +			dst[1] = hex_asc_lo(ch);  
> > 
> > We have hex_pack_byte() or so
> 
> At least some versions of gcc have generated better code if you don't
> use *ptr++ but do the increment afterwards.
> It is also what the old version used.

Do we really care? What versions, btw, are you talk about?

> Not to mention being another wrapper you need to look up to work out
> what the code is doing.

That's not an issue. We use a lot of wrappers in the Linux kernel.
Without a skill to quickly find this information it would be very
hard to develop the kernel code without reinventing a wheel.

...

> > > -		linebuf[lx++] = (isascii(ch) && isprint(ch)) ? ch : '.';
> > > +		*dst++ = ch >= ' ' && ch < 0x7f ? ch : '.';  
> > 
> > Please also add a test case for this to make sure it has no changes.
> 
> Well isascii() usually checks for the 0x80 bit being clear and isprint()
> rejects control characters and 'del' (0x7f).
> I'm not sure what isascii() does for EBCDIC type charsets - but I don't
> expect Linux runs on any of those so who cares.

Still, it's good to have a test cases for this change.

> Oh, and isprint() seems to be based on a memory lookup in an _ctype[] array.
> Very 1970s.

With enough CPU (data) caches it's quite effective.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[Nick Child]

On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:
> Fastpath the normal case of single byte output that fits in the buffer.
> Output byte groups (byteswapped on little-endian) without calling snprintf().
> Remove the restriction that rowsize must be 16 or 32.
> Remove the restriction that groupsize must be 8 or less.
> If groupsize isn't a power of 2 or doesn't divide into both len and
>   rowsize it is set to 1 (otherwise byteswapping is hard).
> Change the types of the rowsize and groupsize parameters to be unsigned types.
>

Thank you!

> Tested in a userspace harness, code size (x86-64) halved to 723 bytes.
> 
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
>  include/linux/printk.h |   6 +-
>  lib/hexdump.c          | 165 ++++++++++++++++++++---------------------
>  2 files changed, 85 insertions(+), 86 deletions(-)
> 
> diff --git a/include/linux/printk.h b/include/linux/printk.h
> index 4217a9f412b2..49e67f63277e 100644
> --- a/include/linux/printk.h
> +++ b/include/linux/printk.h
> @@ -752,9 +752,9 @@ enum {
>  	DUMP_PREFIX_ADDRESS,
>  	DUMP_PREFIX_OFFSET
>  };
...
> - * hex_dump_to_buffer() works on one "line" of output at a time, i.e.,
> + * If @groupsize isn't a power of 2 that divides into both @len and @rowsize
> + * the it is set to 1.

s/the/then/

> + *
> + * hex_dump_to_buffer() works on one "line" of output at a time, e.g.,
>   * 16 or 32 bytes of input data converted to hex + ASCII output.
...
> -		linebuf[lx++] = ' ';
> +	if (!ascii) {
> +		*dst = 0;
> +		return out_len;
>  	}
> + 
> +	pad_len += 2;

So at a minimum there is 2 spaces before the ascii translation?
when people allocate linebuf, what should they use to calculate the len?

Also side nit, this existed before this patch, the endian switch may
occur on the hex dump but it doesn't on the ascii conversion:
[   20.172006][  T150] 706f6e6d6c6b6a696867666564636261  abcdefghijklmnop


> +	out_len += pad_len + len;
> +	if (dst + pad_len >= dst_end)
> +		pad_len = dst_end - dst - 1;

Why not jump to hex_truncate here? This feels like an error case and
if I am understanding correctly, this will pad the rest of the buffer
leaving no room for ascii.

> +	while (pad_len--)
> +		*dst++ = ' ';
> +
> +	if (dst + len >= dst_end)
...
> -- 
> 2.39.5

I will like to also support a wrapper to a bitmap argument as Andy
mentioned. Mostly for selfish reasons though: I would like an argument
to be added to skip endian conversion, and just observe the bytes as they
appear in memory (without having to use groupsize 1).

I had fun tracking some of these bitwise operations on power of 2
integers, I think I must've missed that day in school. Cool stuff :)

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[David Laight]

On Tue, 18 Feb 2025 16:52:38 -0600
Nick Child <nnac123@linux.ibm.com> wrote:

> On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:
> > Fastpath the normal case of single byte output that fits in the buffer.
> > Output byte groups (byteswapped on little-endian) without calling snprintf().
> > Remove the restriction that rowsize must be 16 or 32.
> > Remove the restriction that groupsize must be 8 or less.
> > If groupsize isn't a power of 2 or doesn't divide into both len and
> >   rowsize it is set to 1 (otherwise byteswapping is hard).
> > Change the types of the rowsize and groupsize parameters to be unsigned types.
> >  
> 
> Thank you!
> 
> > Tested in a userspace harness, code size (x86-64) halved to 723 bytes.
> > 
> > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > ---
> >  include/linux/printk.h |   6 +-
> >  lib/hexdump.c          | 165 ++++++++++++++++++++---------------------
> >  2 files changed, 85 insertions(+), 86 deletions(-)
> > 
> > diff --git a/include/linux/printk.h b/include/linux/printk.h
> > index 4217a9f412b2..49e67f63277e 100644
> > --- a/include/linux/printk.h
> > +++ b/include/linux/printk.h
> > @@ -752,9 +752,9 @@ enum {
> >  	DUMP_PREFIX_ADDRESS,
> >  	DUMP_PREFIX_OFFSET
> >  };  
> ...
> > - * hex_dump_to_buffer() works on one "line" of output at a time, i.e.,
> > + * If @groupsize isn't a power of 2 that divides into both @len and @rowsize
> > + * the it is set to 1.  
> 
> s/the/then/
> 
> > + *
> > + * hex_dump_to_buffer() works on one "line" of output at a time, e.g.,
> >   * 16 or 32 bytes of input data converted to hex + ASCII output.  
> ...
> > -		linebuf[lx++] = ' ';
> > +	if (!ascii) {
> > +		*dst = 0;
> > +		return out_len;
> >  	}
> > + 
> > +	pad_len += 2;  
> 
> So at a minimum there is 2 spaces before the ascii translation?

That is the way it always was.
Does make sense that way.

> when people allocate linebuf, what should they use to calculate the len?

Enough :-)
Unchanged from before, 'rowsize * 4 + 2' is just enough.

> 
> Also side nit, this existed before this patch, the endian switch may
> occur on the hex dump but it doesn't on the ascii conversion:
> [   20.172006][  T150] 706f6e6d6c6b6a696867666564636261  abcdefghijklmnop

Correct, that is what you want.
Consider { u32 x; char y[4]; } - you don't want the ascii byte reversed.

Indeed, if the data might not be aligned it is easier to process the
hex bytes in address order than a little-endian value that is split
between two 'words'. 

> 
> 
> > +	out_len += pad_len + len;
> > +	if (dst + pad_len >= dst_end)
> > +		pad_len = dst_end - dst - 1;  
> 
> Why not jump to hex_truncate here? This feels like an error case and
> if I am understanding correctly, this will pad the rest of the buffer
> leaving no room for ascii.

I missed that, can't remember what the old code did.

> 
> > +	while (pad_len--)
> > +		*dst++ = ' ';
> > +
> > +	if (dst + len >= dst_end)  
> ...
> > -- 
> > 2.39.5  
> 
> I will like to also support a wrapper to a bitmap argument as Andy
> mentioned. Mostly for selfish reasons though: I would like an argument
> to be added to skip endian conversion, and just observe the bytes as they
> appear in memory (without having to use groupsize 1).

More useful would be an option to keep address order with a space
between the bytes, but add an extra space every 'n' bytes.
So you get: "00 11 22 33  44 55 66 77  88..."

But that is an enhancement rather than a rewrite.
Although it is all easier to do with my new 'slow path' loop.

> I had fun tracking some of these bitwise operations on power of 2
> integers, I think I must've missed that day in school. Cool stuff :)

It came the day after the rule for inverting boolean expressions.

	David

Re: [PATCH next 1/1] lib: Optimise hex_dump_to_buffer()

[David Laight]

On Tue, 18 Feb 2025 16:52:38 -0600
Nick Child <nnac123@linux.ibm.com> wrote:

> On Sun, Feb 16, 2025 at 08:19:01PM +0000, David Laight wrote:
> > Fastpath the normal case of single byte output that fits in the buffer.
> > Output byte groups (byteswapped on little-endian) without calling snprintf().
> > Remove the restriction that rowsize must be 16 or 32.

That lets dump_hex_to_buffer(buf, len, len, 1, output, size, true) be used
to format hex+ascii without a gap between the hex and ascii.

> > Remove the restriction that groupsize must be 8 or less.
> > If groupsize isn't a power of 2 or doesn't divide into both len and
> >   rowsize it is set to 1 (otherwise byteswapping is hard).
> > Change the types of the rowsize and groupsize parameters to be unsigned types.
> >  
> 
> Thank you!
> 
....
> > +	out_len += pad_len + len;
> > +	if (dst + pad_len >= dst_end)
> > +		pad_len = dst_end - dst - 1;  
> 
> Why not jump to hex_truncate here? This feels like an error case and
> if I am understanding correctly, this will pad the rest of the buffer
> leaving no room for ascii.

I've had a look at the code again.
The truncating error path would be: dst[0] = 0; return out_len;
But that would be confusing because it would be a truncated output that
doesn't fill the buffer.
This is different from snprintf(), so I think it is best to pad to the
end of the buffer.

	David