Documentation of memcpy and undefined behavior in memset

Documentation of memcpy and undefined behavior in memset

[Pascal Cuoq]

[-- Attachment #1: Type: text/plain, Size: 2022 bytes --]

Hello all,

when I started testing parts of musl with TIS Interpreter, I made sure to use TIS Interpreter versions of low-level functions such as memcpy and memset, while testing higher-level functions. Musl's functions can provide guarantees beyond the standard, and it is fair game to rely on these guarantees elsewhere in musl since musl's versions of these functions are called, but I thought it would be interesting to know that musl provides additional guarantees and relies on them.

That was informative. It turned out that musl's implementation of fwrite() can call memcpy() with a length of 0 and a pointer one-past, inside __fwritex:

https://git.musl-libc.org/cgit/musl/tree/src/stdio/fwrite.c?id=a08910fc2cc739f631b75b2d09b8d72a0d64d285#n23

It can be argued that C11 does not define the behavior of memcpy in this case: https://stackoverflow.com/questions/25390577/is-memcpya-1-b-1-0-defined-in-c11

For this reason, it may be worth documenting that musl's memcpy does not require valid pointers when invoked with a size of 0, and any future memcpy implementation (e.g. in assembly) should continue to do so.


Changing course and using musl's implementation of memcpy and memset to analyse higher-level functions, we found what I think is an undefined behavior in memset. The following line in the implementation of memset can be reached with n = 1:


s[0] = s[n-1] = c;

https://git.musl-libc.org/cgit/musl/tree/src/string/memset.c?id=a08910fc2cc739f631b75b2d09b8d72a0d64d285#n14

I think this is undefined because i = i++;, which is equivalent to i = i = i + 1;, is the canonical example for the “unsequenced side-effect in expression” undefined behavior(*), and what makes this latter example undefined is the “i = i =” part, not the “i + 1” part. Musl's “s[0] = s[n-1] =” is identical to that when n == 1.
The same problem occurs in the next lines of memset for other values of n.

Pascal

(*) https://en.wikipedia.org/wiki/Sequence_point#Examples_of_ambiguity

[-- Attachment #2: Type: text/html, Size: 3572 bytes --]

Re: Documentation of memcpy and undefined behavior in memset

[Alexander Monakov]

On Thu, 6 Jul 2017, Pascal Cuoq wrote:
> It can be argued that C11 does not define the behavior of memcpy in this case:
> https://stackoverflow.com/questions/25390577/is-memcpya-1-b-1-0-defined-in-c11

Is the main issue that there are doubts whether pointers one-past may be
"outside the address space of the program"? To me it's pretty clear that
while the standard doesn't appear to formally define the "address space",
the intent is that pointers one-past would be a part of it for. There are
indications in 6.5.8/5 ("When two pointers are compared, the result
depends on the relative locations in the address space of the objects
pointed to...") and footnote 106 to 6.5.6 in C11.

Alexander

Re: Documentation of memcpy and undefined behavior in memset

[Rich Felker]

On Thu, Jul 06, 2017 at 02:15:25PM +0000, Pascal Cuoq wrote:
> Hello all,
> 
> when I started testing parts of musl with TIS Interpreter, I made
> sure to use TIS Interpreter versions of low-level functions such as
> memcpy and memset, while testing higher-level functions. Musl's
> functions can provide guarantees beyond the standard, and it is fair
> game to rely on these guarantees elsewhere in musl since musl's
> versions of these functions are called, but I thought it would be
> interesting to know that musl provides additional guarantees and
> relies on them.
> 
> That was informative. It turned out that musl's implementation of
> fwrite() can call memcpy() with a length of 0 and a pointer
> one-past, inside __fwritex:
> 
> https://git.musl-libc.org/cgit/musl/tree/src/stdio/fwrite.c?id=a08910fc2cc739f631b75b2d09b8d72a0d64d285#n23
> 
> It can be argued that C11 does not define the behavior of memcpy in
> this case:
> https://stackoverflow.com/questions/25390577/is-memcpya-1-b-1-0-defined-in-c11
> 
> For this reason, it may be worth documenting that musl's memcpy does
> not require valid pointers when invoked with a size of 0, and any
> future memcpy implementation (e.g. in assembly) should continue to
> do so.

FWIW, I think GCC may do aggressive optimization based on the
assumption that memcpy implies the pointer points to an object (of
size at least 1), and if so, we really are depending on -ffreestanding
here (i.e. disallowing the compiler to assume semantics of standard
functions). I'd probably rather, in the long term, avoid such calls to
memcpy, if for no other reason than encouraging correct usage by
example (also possibly helping people who reuse the code outside of
libc).

> Changing course and using musl's implementation of memcpy and memset
> to analyse higher-level functions, we found what I think is an
> undefined behavior in memset. The following line in the
> implementation of memset can be reached with n = 1:
> 
> 
> s[0] = s[n-1] = c;
> 
> https://git.musl-libc.org/cgit/musl/tree/src/string/memset.c?id=a08910fc2cc739f631b75b2d09b8d72a0d64d285#n14
> 
> I think this is undefined because i = i++;, which is equivalent to i
> = i = i + 1;, is the canonical example for the “unsequenced
> side-effect in expression” undefined behavior(*), and what makes
> this latter example undefined is the “i = i =” part, not the “i + 1”
> part. Musl's “s[0] = s[n-1] =” is identical to that when n == 1. The
> same problem occurs in the next lines of memset for other values of
> n.

I think you're correct, at least under a pessimistic interpretation of
the standard. I can't find where they actually define "modifies", and
you could argue that assignment of the same value twice "modifies" the
object at most once, but I don't like relying on that kind of
ambiguity and it's easy enough to fix just by adding a sequence point.

Rich

Re: Documentation of memcpy and undefined behavior in memset

[Alexander Monakov]

On Thu, 6 Jul 2017, Rich Felker wrote:
> FWIW, I think GCC may do aggressive optimization based on the
> assumption that memcpy implies the pointer points to an object (of
> size at least 1)

The compiler can deduce that the pointer is non-null (and that's
fine), but otherwise I don't see what possible optimizations could
take place. Did you have something specific in mind?

Alexander

Re: Documentation of memcpy and undefined behavior in memset

[Rich Felker]

On Thu, Jul 06, 2017 at 08:02:12PM +0300, Alexander Monakov wrote:
> On Thu, 6 Jul 2017, Rich Felker wrote:
> > FWIW, I think GCC may do aggressive optimization based on the
> > assumption that memcpy implies the pointer points to an object (of
> > size at least 1)
> 
> The compiler can deduce that the pointer is non-null (and that's
> fine), but otherwise I don't see what possible optimizations could
> take place. Did you have something specific in mind?

It could presumably move loads from after a branch to before. E.g.

	memcpy(q,p,0);
	if (whatever) {
		y=*p;
		...
	}
	/* y not used after here */

to:

	memcpy(q,p,0);
	y=*p;
	if (whatever) {
		...
	}
	/* y not used after here */

If p points to one past the end of an object that ends on a page
boundary, this transformation could introduce a crash.

Rich

Re: Documentation of memcpy and undefined behavior in memset

[Alexander Monakov]

On Thu, 6 Jul 2017, Rich Felker wrote:

> If p points to one past the end of an object that ends on a page
> boundary, this transformation could introduce a crash.

The object beginning at p (i.e. the array beginning just after the
array which p was derived from) could be volatile, making that an
invalid transformation. Nothing gives the compiler a guarantee
that that area is non-volatile.

Alexander

Re: Documentation of memcpy and undefined behavior in memset

[Rich Felker]

On Thu, Jul 06, 2017 at 08:17:32PM +0300, Alexander Monakov wrote:
> On Thu, 6 Jul 2017, Rich Felker wrote:
> 
> > If p points to one past the end of an object that ends on a page
> > boundary, this transformation could introduce a crash.
> 
> The object beginning at p (i.e. the array beginning just after the
> array which p was derived from) could be volatile, making that an
> invalid transformation. Nothing gives the compiler a guarantee
> that that area is non-volatile.

I'm doubtful of this. Certainly passing a pointer to memcpy with a
nonzero n is a guarantee that the pointed-to object is non-volatile.
The n=0 case is less clear though.

Rich

Re: Documentation of memcpy and undefined behavior in memset

[Alexander Monakov]

On Thu, 6 Jul 2017, Rich Felker wrote:

> I'm doubtful of this. Certainly passing a pointer to memcpy with a
> nonzero n is a guarantee that the pointed-to object is non-volatile.
> The n=0 case is less clear though.

My view is that since in n=0 case no memory access inside of memcpy
takes place, the compiler may not deduce that the pointed-to object is
ok for speculative reads.

Alexander

Re: Documentation of memcpy and undefined behavior in memset

[Rich Felker]

On Thu, Jul 06, 2017 at 08:38:29PM +0300, Alexander Monakov wrote:
> On Thu, 6 Jul 2017, Rich Felker wrote:
> 
> > I'm doubtful of this. Certainly passing a pointer to memcpy with a
> > nonzero n is a guarantee that the pointed-to object is non-volatile.
> > The n=0 case is less clear though.
> 
> My view is that since in n=0 case no memory access inside of memcpy
> takes place, the compiler may not deduce that the pointed-to object is
> ok for speculative reads.

Indeed, I think that's a valid interpretation, but not the only one;
the problem here is that the specification is ambiguous, and I suspect
nobody wants to fix the ambiguity because they know they're going to
have an argument over what it was intended to mean...

Rich

Re: Documentation of memcpy and undefined behavior in memset

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1734 bytes --]

Hello,

On Thu, 6 Jul 2017 14:13:26 -0400 Rich Felker <dalias@libc.org> wrote:

> On Thu, Jul 06, 2017 at 08:38:29PM +0300, Alexander Monakov wrote:
> > On Thu, 6 Jul 2017, Rich Felker wrote:
> >   
> > > I'm doubtful of this. Certainly passing a pointer to memcpy with a
> > > nonzero n is a guarantee that the pointed-to object is
> > > non-volatile. The n=0 case is less clear though.  
> > 
> > My view is that since in n=0 case no memory access inside of memcpy
> > takes place, the compiler may not deduce that the pointed-to object
> > is ok for speculative reads.  
> 
> Indeed, I think that's a valid interpretation, but not the only one;
> the problem here is that the specification is ambiguous, and I suspect
> nobody wants to fix the ambiguity because they know they're going to
> have an argument over what it was intended to mean...

No, no, not because of that :)

More seriously, if there is existing practice in both ways, the
committee would not want to invalidate any of them for just a TC. In
consequence, as a user of such functions you'd always have to be
conservative. As an implementor, you can basically chose, but this
doesn't help much because your users can't rely on that particular
behavior.

Now when it comes to changes for a new standard, people would certainly
be more open-minded. So if anybody thinks they want to make a proposal
for C2x, don't hesitate.

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

[-- Attachment #2: Digitale Signatur von OpenPGP --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: Documentation of memcpy and undefined behavior in memset

[Szabolcs Nagy]

* Jens Gustedt <jens.gustedt@inria.fr> [2017-07-06 20:52:18 +0200]:
> Now when it comes to changes for a new standard, people would certainly
> be more open-minded. So if anybody thinks they want to make a proposal
> for C2x, don't hesitate.

i wonder if c2x design will be done more openly
than usual wg14 practice.. otherwise there is no
point comming up with proposals, they won't even
look at it until some member presents the idea
at a meeting.

Re: Documentation of memcpy and undefined behavior in memset

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 2336 bytes --]

Hello,

On Thu, 6 Jul 2017 21:23:07 +0200 Szabolcs Nagy <nsz@port70.net> wrote:

> * Jens Gustedt <jens.gustedt@inria.fr> [2017-07-06 20:52:18 +0200]:
> > Now when it comes to changes for a new standard, people would
> > certainly be more open-minded. So if anybody thinks they want to
> > make a proposal for C2x, don't hesitate.  
> 
> i wonder if c2x design will be done more openly
> than usual wg14 practice.. otherwise there is no
> point comming up with proposals, they won't even
> look at it until some member presents the idea
> at a meeting.

WG14 practice is to be conservative for the sake of backwards
compatibility. If you bring in new ideas, you have to be very careful
to convince people of your point and that it fits well into the
existing. They (mostly) want to standardize common practice, so if
there are reference implementations for your ideas, the better.

If you don't have anybody at the meeting to defend an idea, it is just
hard to defend it. That is not different than in other
organizations. If you are working for a company/institution that can
afford this, convince them that you want to go to the meetings. This
is two weeks a year, with some travel cost, something like 5000 € /
year or so (without the work cost) should do. This is our industry, C
is an important part of it and I really don't understand why there are
not more companies sending their people. This is not a big
investment. (But they do send them to the C++ meetings instead, e.g,
perhaps because it's more fancy?)

If you can't afford to go to the meetings, speak to a member, try to
get feedback on your ideas. Co-author DRs or proposals, and see for
yourself how your ideas fit into the standard.

I think musl would be a perfect code base to try new things out that
are related to the C library. (Not meaning to integrate extension into
the distribution, but to build demonstrators.) But this is not enough,
a thorrow write up must follow, and you'd have to have some breath.


Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

[-- Attachment #2: Digitale Signatur von OpenPGP --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: Documentation of memcpy and undefined behavior in memset

[Bartosz Brachaczek]

On 7/6/2017 6:23 PM, Rich Felker wrote:
> I think you're correct, at least under a pessimistic interpretation of
> the standard. I can't find where they actually define "modifies", and
> you could argue that assignment of the same value twice "modifies" the
> object at most once, but I don't like relying on that kind of
> ambiguity and it's easy enough to fix just by adding a sequence point.

I don't have a copy of C11, but N1570 reads in a note to 3.1:

> ‘‘Modify’’ includes the case where the new value being stored is the same as the previous value.

Bartosz

Re: Documentation of memcpy and undefined behavior in memset

[Leah Neukirchen]

Bartosz Brachaczek <b.brachaczek@gmail.com> writes:

> On 7/6/2017 6:23 PM, Rich Felker wrote:
>> I think you're correct, at least under a pessimistic interpretation of
>> the standard. I can't find where they actually define "modifies", and
>> you could argue that assignment of the same value twice "modifies" the
>> object at most once, but I don't like relying on that kind of
>> ambiguity and it's easy enough to fix just by adding a sequence point.
>
> I don't have a copy of C11, but N1570 reads in a note to 3.1:
>
>> ‘‘Modify’’ includes the case where the new value being stored is the
>> same as the previous value.

C11 also specifies a sequence for assignment (6.5.16.3):

> The side effect of updating the stored value of the left operand is
> sequenced after the value computations of the left and right
> operands.

-- 
Leah Neukirchen  <leah@vuxu.org>  http://leah.zone

Re: Documentation of memcpy and undefined behavior in memset

[Szabolcs Nagy]

* Leah Neukirchen <leah@vuxu.org> [2017-07-06 21:10:31 +0200]:
> Bartosz Brachaczek <b.brachaczek@gmail.com> writes:
> 
> > On 7/6/2017 6:23 PM, Rich Felker wrote:
> >> I think you're correct, at least under a pessimistic interpretation of
> >> the standard. I can't find where they actually define "modifies", and
> >> you could argue that assignment of the same value twice "modifies" the
> >> object at most once, but I don't like relying on that kind of
> >> ambiguity and it's easy enough to fix just by adding a sequence point.
> >
> > I don't have a copy of C11, but N1570 reads in a note to 3.1:
> >
> >> ‘‘Modify’’ includes the case where the new value being stored is the
> >> same as the previous value.
> 
> C11 also specifies a sequence for assignment (6.5.16.3):
> 
> > The side effect of updating the stored value of the left operand is
> > sequenced after the value computations of the left and right
> > operands.

yes, unfortunately the value computation of the right
operand can be unsequenced wrt the side effect of the
right operand..

but since expression evaluation with side effects is
not specified in great detail it's hard to tell.

Re: Documentation of memcpy and undefined behavior in memset

[Szabolcs Nagy]

* Pascal Cuoq <cuoq@trust-in-soft.com> [2017-07-06 14:15:25 +0000]:
> 
> s[0] = s[n-1] = c;
> 
> https://git.musl-libc.org/cgit/musl/tree/src/string/memset.c?id=a08910fc2cc739f631b75b2d09b8d72a0d64d285#n14
> 
> I think this is undefined because i = i++;, which is equivalent to i = i = i + 1;, is the canonical example for the “unsequenced side-effect in expression” undefined behavior(*), and what makes this latter example undefined is the “i = i =” part, not the “i + 1” part. Musl's “s[0] = s[n-1] =” is identical to that when n == 1.
> The same problem occurs in the next lines of memset for other values of n.
> 

i think it's wrong to say that i = i++ is equivalent to i = i = i+1,
since i=i+1 is not the same as i++ (it is almost the same as ++i but
actually subtly different when considering sequencing evaluations so
such analogy is just confusing).

you can say that you think i = i = 0 is ub.

i think the key is that the value computation of an assignment
expression is not sequenced after its side effect (store) (note
that the value computations of the operands are sequenced before it),
so there are two unsequenced stores to the same object, this is not
very obvious from the text of the standard though.