Re: [PATCH v4 01/34] lib/printbuf: New data structure for printing strings

[Kent Overstreet]

On Mon, Jun 20, 2022 at 03:53:38PM +0000, David Laight wrote:
> From: Kent Overstreet
> > Sent: 20 June 2022 16:31
> > 
> > On Mon, Jun 20, 2022 at 04:44:10AM +0000, David Laight wrote:
> > > From: Kent Overstreet
> > > > Sent: 20 June 2022 01:42
> > > >
> > > > This adds printbufs: a printbuf points to a char * buffer and knows the
> > > > size of the output buffer as well as the current output position.
> > > >
> > > > Future patches will be adding more features to printbuf, but initially
> > > > printbufs are targeted at refactoring and improving our existing code in
> > > > lib/vsprintf.c - so this initial printbuf patch has the features
> > > > required for that.
> > > >
> > > > Signed-off-by: Kent Overstreet <kent.overstreet@xxxxxxxxx>
> > > > Reviewed-by: Matthew Wilcox (Oracle) <willy@xxxxxxxxxxxxx>
> > > > ---
> > > >  include/linux/printbuf.h | 122 +++++++++++++++++++++++++++++++++++++++
> > > >  1 file changed, 122 insertions(+)
> > > >  create mode 100644 include/linux/printbuf.h
> > > >
> > > > diff --git a/include/linux/printbuf.h b/include/linux/printbuf.h
> > > > new file mode 100644
> > > > index 0000000000..8186c447ca
> > > > --- /dev/null
> > > > +++ b/include/linux/printbuf.h
> > > > @@ -0,0 +1,122 @@
> > > > +/* SPDX-License-Identifier: LGPL-2.1+ */
> > > > +/* Copyright (C) 2022 Kent Overstreet */
> > > > +
> > > > +#ifndef _LINUX_PRINTBUF_H
> > > > +#define _LINUX_PRINTBUF_H
> > > > +
> > > > +#include <linux/kernel.h>
> > > > +#include <linux/string.h>
> > > > +
> > > > +/*
> > > > + * Printbufs: String buffer for outputting (printing) to, for vsnprintf
> > > > + */
> > > > +
> > > > +struct printbuf {
> > > > +	char			*buf;
> > > > +	unsigned		size;
> > > > +	unsigned		pos;
> > >
> > > No naked unsigneds.
> > 
> > This is the way I've _always_ written kernel code - single word type names.
> 
> I'm pretty sure the coding standards require 'int'.

I've been contributing code to the kernel for many years and I'm picky about my
style, I'm not about to change now.

> 
> > >
> > > > +};
> > > > +
> > > > +/*
> > > > + * Returns size remaining of output buffer:
> > > > + */
> > > > +static inline unsigned printbuf_remaining_size(struct printbuf *out)
> > > > +{
> > > > +	return out->pos < out->size ? out->size - out->pos : 0;
> > > > +}
> > > > +
> > > > +/*
> > > > + * Returns number of characters we can print to the output buffer - i.e.
> > > > + * excluding the terminating nul:
> > > > + */
> > > > +static inline unsigned printbuf_remaining(struct printbuf *out)
> > > > +{
> > > > +	return out->pos < out->size ? out->size - out->pos - 1 : 0;
> > > > +}
> > >
> > > Those two are so similar mistakes will be make.
> > 
> > If you've got ideas for better names I'd be happy to hear them - we discussed
> > this and this was what we came up with.
> > 
> > > You can also just return negatives when the buffer has overlowed
> > > and get the callers to test < or <= as required.
> > 
> > Yeesh, no.
> 
> Why not?
> All the callers are internal.
> It saves a test and branch (or cmove).

Because this is a subtle thing and having two separate helpers better documents
the _intent_ of the code. I prioritize having clear and understandable code over
shaving every branch.

printbuf_remaining() is the one almost all callers want to use;
printbuf_remaining_size() is only for a few callers that are doing weird things
and should probably be converted to something more standard.

> 
> > > I also wonder it is necessary to count the total length
> > > when the buffer isn't long enough?
> > > Unless there is a real pressing need for it I'd not bother.
> > > Setting pos == size (after writing the '\0') allows
> > > overflow be detected without most of the dangers.
> > 
> > Because that's what snprintf() needs.
> > 
> > > > +
> > > > +static inline unsigned printbuf_written(struct printbuf *out)
> > > > +{
> > > > +	return min(out->pos, out->size);
> > >
> > > That excludes the '\0' for short buffers but includes
> > > it for overlong ones.
> > 
> > It actually doesn't.
> 
> If size is 2 it goes 0, 1, 2, 2, 2 as bytes are added.
> But the string is "" "a" "a" "a" - never 2 characters. 

Ah, you're right. Ok, that's a bug, I'll fix that.

> As opposed to the one in strlen() ?
> I realise that there are shift and mask algorithms from strlen()
> that are likely faster than a byte scan on 64 bit systems.
> But they are likely slower than the check when you have a loop
> that is scanning byte by byte.
> This is especially true on out of order superscaler cpu when
> the copy loop won't be using all the execution blocks.
> 
> What might be faster on cpu (like x86) where misaligned memory
> access are almost entirely free is to copy 8 bytes at a time
> while checking for a zero at the same time.
> 
> Remember kernel strings are quite often short, the overhead
> costs for 'fast' routines slow things down.
> (As you found when calling memcpy() and memset().)

Look, from scanning the kernel log I get you're the kind of programmer who likes
shaving every branch and instruction.

I've spent a _lot_ of time in my career staring at profiles and assembly and
counting cycles (and was working with someone juinor doing that just last
night), and what I've found over the years is that time and again...  it's
memory accesses and cache misses that matter, and not much else.

I put a lot of effort into writing high performance code, and what I find is
that my time is better spent when I focus on writing clear and understandable
code, and making sure that things are laid out in memory intelligently, instead
of trying to generate the "perfect" assembly from all the code I write.

Perfect can be the enemy of good.

If you want to submit patches later optimizing this stuff, be my guest - _but_,
if it comes at the cost of making the code harder to read I'll want to see
benchmark improvements, and of more than a few percent here and there.