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

[Alejandro Colomar <alx.manpages@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 6088 bytes --]



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().

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?

> }
>>
>> 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/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]