Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.c > #160379 > unrolled thread

"oversized" memchr/wmemchr: UB or not?

Started byKaz Kylheku <563-365-8930@kylheku.com>
First post2021-04-26 21:33 +0000
Last post2021-04-26 20:36 -0700
Articles 5 — 3 participants

Back to article view | Back to comp.lang.c


Contents

  "oversized" memchr/wmemchr: UB or not? Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-26 21:33 +0000
    Re: "oversized" memchr/wmemchr: UB or not? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-26 14:55 -0700
      Re: "oversized" memchr/wmemchr: UB or not? Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-27 00:31 +0000
        Re: "oversized" memchr/wmemchr: UB or not? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-26 21:34 -0700
    Re: "oversized" memchr/wmemchr: UB or not? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2021-04-26 20:36 -0700

#160379 — "oversized" memchr/wmemchr: UB or not?

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-26 21:33 +0000
Subject"oversized" memchr/wmemchr: UB or not?
Message-ID<20210426141232.677@kylheku.com>
Suppose we have this:

   const *s = "abc";

s[3] is obviously a null byte.

Is this well-defined?

   memchr(s, 0, 5)?

You would think so, because although s does not point to a five byte
object, the function is supposed to find the first null among the bytes.
It will find the null at s[3], which prevents accessing s[4].

But the standard has wording for memchr and wmemchr very similar to
"searches the initial n characters of the object pointed at by s".

There are no "the initial 5 characters of the object pointed at by s"
in our example; the object simply does not have 5 characters.

The requirement is to find the "first occurrence", but there is no
requirement that this be done in a left-to-right search.

It seems an implementation would be conforming if it scanned the
object from right to left, and then reported the most recently seen
pointer, if any, which pointed at the sought-after value.

According to this possibility, the behavior is not well defined if the
size overestimates the actual object.

Come to think of it, we can come up with a similar question for memcmp.

Suppose we have:

   char a[3] = "ab$";
   char b[8] = "abcdefgh";

Does

   memcmp(a, b, 8);

work from left to right and stop at the first mismatch '$' versus 'c'?
Or is it allowed to assume that both objects have at least 6 bytes, and
do the comparison in any order, resulting on out-of-bounds access?

There are programs that would work under the left-to-right
interpretation, if they somehow know that there is always a guaranteed
mismatching character in the shorter object.

Suppose the implementation takes some short-cut, like loading 8 bytes
from each location and compare them as words, to check for an exact
match? a[3] could be just before the end of a page, resulting in a bad
access.


-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [next] | [standalone]


#160382

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2021-04-26 14:55 -0700
Message-ID<87im48bti5.fsf@nosuchdomain.example.com>
In reply to#160379
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> Suppose we have this:
>
>    const *s = "abc";
>
> s[3] is obviously a null byte.
>
> Is this well-defined?
>
>    memchr(s, 0, 5)?
>
> You would think so, because although s does not point to a five byte
> object, the function is supposed to find the first null among the bytes.
> It will find the null at s[3], which prevents accessing s[4].
>
> But the standard has wording for memchr and wmemchr very similar to
> "searches the initial n characters of the object pointed at by s".
>
> There are no "the initial 5 characters of the object pointed at by s"
> in our example; the object simply does not have 5 characters.

N1570 7.24.5.1:

    The memchr function locates the first occurrence of c (converted to
    an unsigned char) in the initial n characters (each interpreted as
    unsigned char) of the object pointed to by s.

This might imply that if there are no "initial n characters", the
behavior is undefined.  However, this is followed by:

    The implementation shall behave as if it reads the characters
    sequentially and stops as soon as a matching character is found.

That's more explicit, and I think the intent is that your call is
well defined.  It could be stated more clearly, though.  If the first
sentence is taken to imply that your call has undefined behavior,
the "shall behave as if" in the second sentence doesn't necessarily
override that.

> The requirement is to find the "first occurrence", but there is no
> requirement that this be done in a left-to-right search.
>
> It seems an implementation would be conforming if it scanned the
> object from right to left, and then reported the most recently seen
> pointer, if any, which pointed at the sought-after value.
>
> According to this possibility, the behavior is not well defined if the
> size overestimates the actual object.
>
> Come to think of it, we can come up with a similar question for memcmp.
>
> Suppose we have:
>
>    char a[3] = "ab$";
>    char b[8] = "abcdefgh";
>
> Does
>
>    memcmp(a, b, 8);
>
> work from left to right and stop at the first mismatch '$' versus 'c'?
> Or is it allowed to assume that both objects have at least 6 bytes, and
> do the comparison in any order, resulting on out-of-bounds access?

The description of memcmp says it "compares the first n characters", and
has no "as if" wording.  I'd say that if examining the first n
characters of both objects would have undefined behavior, then memcmp
would have undefined behavior.

> There are programs that would work under the left-to-right
> interpretation, if they somehow know that there is always a guaranteed
> mismatching character in the shorter object.
>
> Suppose the implementation takes some short-cut, like loading 8 bytes
> from each location and compare them as words, to check for an exact
> match? a[3] could be just before the end of a page, resulting in a bad
> access.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]


#160387

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-27 00:31 +0000
Message-ID<20210426164144.416@kylheku.com>
In reply to#160382
On 2021-04-26, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>> Suppose we have this:
>>
>>    const *s = "abc";
>>
>> s[3] is obviously a null byte.
>>
>> Is this well-defined?
>>
>>    memchr(s, 0, 5)?
>>
>> You would think so, because although s does not point to a five byte
>> object, the function is supposed to find the first null among the bytes.
>> It will find the null at s[3], which prevents accessing s[4].
>>
>> But the standard has wording for memchr and wmemchr very similar to
>> "searches the initial n characters of the object pointed at by s".
>>
>> There are no "the initial 5 characters of the object pointed at by s"
>> in our example; the object simply does not have 5 characters.
>
> N1570 7.24.5.1:
>
>     The memchr function locates the first occurrence of c (converted to
>     an unsigned char) in the initial n characters (each interpreted as
>     unsigned char) of the object pointed to by s.
>
> This might imply that if there are no "initial n characters", the
> behavior is undefined.  However, this is followed by:
>
>     The implementation shall behave as if it reads the characters
>     sequentially and stops as soon as a matching character is found.

Very interesting; this was not found in C99. Therefore a C99
implementation of the library need not implement any interpretation
of this requirement.
>
> That's more explicit, and I think the intent is that your call is
> well defined.  It could be stated more clearly, though.
> If the first
> sentence is taken to imply that your call has undefined behavior,
> the "shall behave as if" in the second sentence doesn't necessarily
> override that.

What we want is something "the implementation shall not access bytes
which follow the first matching byte".  Well, we don't really want that,
because that wording goes too far. Any byte of the object that is okay
to access is contained in a larger word that is also safe to access,
provided it is aligned, and that is part of a useful optimization which
works fine in the case of interest.

The phrase "as if" is not formally defined. Most uses of it in the
document are used to for giving requirements about a programming
language construct by indicating that it must behave "as if"
it were some imaginary augmented or alternative construct.

Those uses of "as if" no way require the implementation to work by
actual trasformation to the alternative construct.

Scanning the object from the right and coming up with the last
occurrence of the character is still "as if" it were being done left to
right to stop at the first occurrence.

By the way, interestingly, though we have this informal concept named
"as if rule" which goes way back, no C standard (that I can get my hands
on between C89 and N1570) uses "as if" in the text that gives the
relationship between abstract and actual semantics.  In other words, the
"as if rule" does not come from any literal quote in a C standard.
The "as if" of "as if rule" does not help here, in any case.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [next] | [standalone]


#160395

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2021-04-26 21:34 -0700
Message-ID<875z08bb1h.fsf@nosuchdomain.example.com>
In reply to#160387
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> On 2021-04-26, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>> Suppose we have this:
>>>
>>>    const *s = "abc";
>>>
>>> s[3] is obviously a null byte.
>>>
>>> Is this well-defined?
>>>
>>>    memchr(s, 0, 5)?
>>>
>>> You would think so, because although s does not point to a five byte
>>> object, the function is supposed to find the first null among the bytes.
>>> It will find the null at s[3], which prevents accessing s[4].
>>>
>>> But the standard has wording for memchr and wmemchr very similar to
>>> "searches the initial n characters of the object pointed at by s".
>>>
>>> There are no "the initial 5 characters of the object pointed at by s"
>>> in our example; the object simply does not have 5 characters.
>>
>> N1570 7.24.5.1:
>>
>>     The memchr function locates the first occurrence of c (converted to
>>     an unsigned char) in the initial n characters (each interpreted as
>>     unsigned char) of the object pointed to by s.
>>
>> This might imply that if there are no "initial n characters", the
>> behavior is undefined.  However, this is followed by:
>>
>>     The implementation shall behave as if it reads the characters
>>     sequentially and stops as soon as a matching character is found.
>
> Very interesting; this was not found in C99. Therefore a C99
> implementation of the library need not implement any interpretation
> of this requirement.

I don't see a DR that refers to memchr, so I don't have a reference to
the rationale for adding that wording.

>> That's more explicit, and I think the intent is that your call is
>> well defined.  It could be stated more clearly, though.
>> If the first
>> sentence is taken to imply that your call has undefined behavior,
>> the "shall behave as if" in the second sentence doesn't necessarily
>> override that.
>
> What we want is something "the implementation shall not access bytes
> which follow the first matching byte".  Well, we don't really want that,
> because that wording goes too far. Any byte of the object that is okay
> to access is contained in a larger word that is also safe to access,
> provided it is aligned, and that is part of a useful optimization which
> works fine in the case of interest.
>
> The phrase "as if" is not formally defined. Most uses of it in the
> document are used to for giving requirements about a programming
> language construct by indicating that it must behave "as if"
> it were some imaginary augmented or alternative construct.
>
> Those uses of "as if" no way require the implementation to work by
> actual trasformation to the alternative construct.
>
> Scanning the object from the right and coming up with the last
> occurrence of the character is still "as if" it were being done left to
> right to stop at the first occurrence.
>
> By the way, interestingly, though we have this informal concept named
> "as if rule" which goes way back, no C standard (that I can get my hands
> on between C89 and N1570) uses "as if" in the text that gives the
> relationship between abstract and actual semantics.  In other words, the
> "as if rule" does not come from any literal quote in a C standard.
> The "as if" of "as if rule" does not help here, in any case.

Ah, but since C99 there's been an index entry for "as-if rule" pointing
to 5.1.2.3, "Program execution".  Paragraph 4 says

    In the abstract machine, all expressions are evaluated as
    specified by the semantics. An actual implementation need not
    evaluate part of an expression if it can deduce that its value is
    not used and that no needed side effects are produced (including
    any caused by calling a function or accessing a volatile object).

and paragraph 6 says:

    The least requirements on a conforming implementation are:

    - Accesses to volatile objects are evaluated strictly according to
      the rules of the abstract machine.

    - At program termination, all data written into files shall be
      identical to the result that execution of the program according to
      the abstract semantics would have produced.

    - The input and output dynamics of interactive devices shall take
      place as specified in 7.21.3. The intent of these requirements is
      that unbuffered or line-buffered output appear as soon as
      possible, to ensure that prompting messages actually appear prior
      to a program waiting for input.

    This is the *observable behavior* of the program.

There's more to that subsection, but those two paragraph seem most
relevant as-if-wise.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]


#160393

FromAndrey Tarasevich <andreytarasevich@hotmail.com>
Date2021-04-26 20:36 -0700
Message-ID<s680st$6v9$1@dont-email.me>
In reply to#160379
On 4/26/2021 2:33 PM, Kaz Kylheku wrote:
 >
 > Come to think of it, we can come up with a similar question for memcmp.
 >
 > Suppose we have:
 >
 >     char a[3] = "ab$";
 >     char b[8] = "abcdefgh";
 >
 > Does
 >
 >     memcmp(a, b, 8);
 >
 > work from left to right and stop at the first mismatch '$' versus 'c'?
 > Or is it allowed to assume that both objects have at least 6 bytes, and
 > do the comparison in any order, resulting on out-of-bounds access?
 >

A question that has been raised quote a few times before, since it is 
connected to obvious optimization opportunities. This 2015 entry by 
Pascal Cuoq

https://trust-in-soft.com/blog/2015/12/21/memcmp-requires-pointers-to-fully-valid-buffers/

points out the difference in wordings for `memchr` and `memcmp`. The 
former explicitly says that "the implementation shall behave as if it 
reads the characters sequentially and stops as soon as a matching 
character is found."

There seems to be no such requirement for `memcmp`. According to the 
link, Glibc implementation of `memcmp` will indeed overstep the 
boundaries of the buffer in both optimization branches: common alignment 
and no common alignment. In the latter case it might overstep by a 
rather large margin, and if circumstances are right it can be shown to 
cause a crash.

-- 
Best regards,
Andrey Tarasevich

[toc] | [prev] | [standalone]


Back to top | Article view | comp.lang.c


csiph-web