Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #160379 > unrolled thread
| Started by | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| First post | 2021-04-26 21:33 +0000 |
| Last post | 2021-04-26 20:36 -0700 |
| Articles | 5 — 3 participants |
Back to article view | Back to comp.lang.c
"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
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-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]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-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]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2021-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