[musl] Documentation of memcpy and undefined behavior in memset

[Pascal Cuoq]

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

[Alexander Monakov]

Post by Pascal Cuoq
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

[Rich Felker]

Post by Pascal Cuoq
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
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
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).

Post by Pascal Cuoq
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
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

[Alexander Monakov]

Post by Rich Felker
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

[Rich Felker]

Post by Alexander Monakov

Post by Rich Felker
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

[Alexander Monakov]

Post by Rich Felker
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

[Rich Felker]

Post by Alexander Monakov

Post by Rich Felker
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

[Alexander Monakov]

Post by Rich Felker
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

[Rich Felker]

Post by Alexander Monakov

Post by Rich Felker
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

[Jens Gustedt]

Hello,

Post by Rich Felker

Post by Alexander Monakov

Post by Rich Felker
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

[Szabolcs Nagy]

Post by Jens Gustedt
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.

[Jens Gustedt]

Hello,

Post by Szabolcs Nagy

Post by Jens Gustedt
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

[Bartosz Brachaczek]

Post by Rich Felker
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.
‘‘Modify’’ includes the case where the new value being stored is the same as the previous value.

Bartosz

[Leah Neukirchen]

Post by Rich Felker
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.
‘‘Modify’’ includes the case where the new value being stored is the
same as the previous value.

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

[Szabolcs Nagy]

Post by Rich Felker
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.
‘‘Modify’’ includes the case where the new value being stored is the
same as the previous value.

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.

[Szabolcs Nagy]

Post by Pascal Cuoq
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.