Re: [PATCH 1/1] string: Add stpecpy(3)

[Noah Goldstein <goldstein.w.n@gmail.com>]

On Sun, Dec 25, 2022 at 4:26 PM Alejandro Colomar
<alx.manpages@gmail.com> wrote:
>
>
>
> On 12/25/22 23:31, Noah Goldstein wrote:
> > On Sun, Dec 25, 2022 at 6:37 AM Alejandro Colomar
> > <alx.manpages@gmail.com> wrote:
> >>
> >> Hi Noah,
> >>
> >> On 12/25/22 02:52, Noah Goldstein wrote:
> >>
> >>>> char *
> >>>> stpecpy (char *dst, char *end, const char *restrict src)
> >>>> {
> >>>>      size_t dsize;
> >>>>      size_t dlen;
> >>>>      size_t slen = strlen (src);
> >>>
> >>> Imo move `dst == end` and `dst == NULL` check before strlen
> >>
> >>
> >> That's a valid optimization.  Having strlen(3) before has the advantage that you
> >> make sure that your strings are strings, as strlcpy(3) does.  But since we're
> >> inventing stpecpy(3), we can choose to be faster.  If anyone wants to instrument
> >> their code, they can add a temporary wrapper that does that.
> >>
> >>> and change strlen to `strnlen(src, dsize)`.
> >>
> >> About strnlen(3), I have doubts.  Isn't strlen(3) faster for the common case of
> >> no truncation or little truncation?  strnlen(3) would optimize for the case
> >> where you truncate by a large difference.
> >
> > It's faster if strlen(s) <= strnlen(s, N) (maybe up to N + 32).
> >
> > But generally I think of it like `qsort`. Most data gets n * log(n) behavior
> > but still it's worth preventing the worst case for minor constant cost.
> >
>
> I.  Maybe it's a good thing.  Since it's a truncating API, I guess optimizing
> for truncation is reasonable.  For common strings, which will be short (size <=
> 64), I guess the constant will really be negligible.
>
> >
> >>
> >>>>      bool   trunc = false;
> >>>>
> >>>>      if (dst == end)
> >>>
> >>> Out of curiosity what if `end < dst`?
> >>
> >> The behavior is undefined.  That's by design.  In the definition of stpecpy(3) I
> >> have currently in libstp, I even tell the compiler to optimize on that condition:
> >> <http://www.alejandro-colomar.es/src/alx/alx/libstp.git/tree/include/stp/stpe/stpecpy.h#n33>
> >>
> >
> > You could probably optimize out one of the branches along the line of:
> > if((dst - 1UL) >= (end - 1UL)) {
> >      // if dst == NULL, then dst - 1UL -> SIZE_MAX and must be >= any value.
>
> You would need a cast, wouldn't you?  Otherwise, you'll get pointer arithmetic.
> Pointer arithmetic with NULL is UB.
>
> >      // if dst == end, then (dst - 1UL) >= (end - 1UL) will be true.
> >      return NULL;
>
> Returning NULL on truncation would be a possibility, but then we'd need to use
> errno to tell the user if the error was truncation or an input NULL (which
> reports an error to a previous vsnprintf(3) call wrapped by [v]stpeprintf().

I'm not sure I see what you mean. Your current logic is:
```
   if (dst == end)
     return NULL;
   if (dst == NULL)
     return NULL;
```
Equivalent (since dst >= end || dst == NULL is required) is:
```
if((dst - 1UL) >= (end - 1UL)) {
    return NULL;
}
```
May need to be cast to a `uintptr` or something but don't see
what you mean about needing to check errno and such.

>
> Using errno would probably counter any optimization, since you'd still need one
> more branch for setting errno, so I guess it's simpler to just use end for
> truncation.
>
>
> Oooor, if we reimplement __vsnprintf_internal(3) to work on size_t and never
> fail, then we could add a [v]stpeprintf(3) that never fails, and then this
> function would only bail out on truncation.
>
> Would it be possible to make __vsnprintf_internal() never fail?  What are the
> current failing conditions; only a size greater than INT_MAX, or are there more
> errors?

Don't think its worth reimplementing    __vsnprintf_internal to save a single
branch here.
>
> > }
> >>
> >> alx@asus5775:~/src/alx/libstp$ grepc -tfd stpecpy
> >> ./include/stp/stpe/stpecpy.h:21:
> >> inline char *stp_nullable
> >> stpecpy(char *stp_nullable dst, char *end, const char *restrict src)
> >> {
> >>          bool    trunc;
> >>          size_t  dsize, dlen, slen;
> >>
> >>          slen = strlen(src);
> >>
> >>          if (dst == end)
> >>                  return end;
> >>          if (stp_unlikely(dst == NULL))  // Allow chaining with stpeprintf().
> >>                  return NULL;
> >>          stp_impossible(dst > end);
> >>
> >>          dsize = end - dst;
> >>          trunc = (slen >= dsize);
> >>          dlen = trunc ? dsize - 1 : slen;
> >>          dst[dlen] = '\0';
> >>
> >>          return mempcpy(dst, src, dlen) + trunc;
> >> }
> >> alx@asus5775:~/src/alx/libstp$ grepc -tm stp_impossible
> >> ./include/stp/_compiler.h:14:
> >> #define stp_impossible(e)   do                                                \
> >> {                                                                             \
> >>          if (e)                                                                \
> >>                  stp_unreachable();                                            \
> >> } while (0)
> >> alx@asus5775:~/src/alx/libstp$ grep -rnC1 define.stp_unreachable
> >> include/stp/_compiler.h-28-#if defined(unreachable)
> >> include/stp/_compiler.h:29:# define stp_unreachable()  unreachable()
> >> include/stp/_compiler.h-30-#else
> >> include/stp/_compiler.h:31:# define stp_unreachable()  __builtin_unreachable()
> >> include/stp/_compiler.h-32-#endif
> >>
> >>
> >> I'd do that for glibc, but I don't see any facility.  Maybe we should add an
> >> __impossible() macro to document UB, and help the compiler.
> >
> > Does it result in any improved codegen? If not seems like
> > making it fail more noisily is always a win.
>
> Both Clang and GCC generate the same code with or without the hint that it's
> impossible.  Anyway, I'll keep it in my source code because it also helps tell
> the programmer that dst>end was taken into consideration and explicitly outlawed.
>
> The 'end' pointer is expected to be always generated as 'buf + sizeof(buf)'.
> Doing something different is not what this API is designed for, and should be
> warned by compilers.  'end' should be a pointer to one after the last byte in an
> array.  Thus, no valid pointer can be greater than end.  If you use this API as
> expected, which is, only chain it with itself and with stpeprintf(3), then it is
> impossible to have dst>end.  But as always, GIGO.
>
> As for the expected result, it would be akin calling strlcpy(3) with a negative
> size.  It would wrap around size_t, and give something close to 2^64.  Both
> would result in a buffer overrun, so writing at random memory, and later a
> crash, but I don't expect that libc should try to detect if the input to
> strlcpy(3) (or actually, any mem*() function) is huge, and neither if input to
> stpecpy(3) is similarly broken.
>
> --
> <http://www.alejandro-colomar.es/>