[musl] un-UBify-strings

[Rich Felker]

I've had this patch sitting around since 2016, and just updated it to
apply cleanly. Any objections? Since I killed the stdio UB in this
release cycle I'd like to go ahead and eliminate all the
string-function UB that can be eliminated (there's still aligned read
past end of string that's unfixable without an attribute that
explicitly allows it, or asm; it might turn out that asm would make
sense here).

Rich

[Pascal Cuoq]

Hello Rich,

On 23 Sep 2018, at 02:35, Rich Felker <***@libc.org<mailto:***@libc.org>> wrote:

I've had this patch sitting around since 2016, and just updated it to
apply cleanly. Any objections?

Your patch contains:

...
size_t __attribute__((__may_alias__)) *wd;
const size_t __attribute__((__may_alias__)) *ws;
...

In my experience, this use of __may_alias__ does not do anything. See function f in the example below, which both GCC and Clang optimize as if the programmer had not used __may_alias__ at all: https://gcc.godbolt.org/z/Um4NU7

You should use a typdef for the aliasing type, as shown for function g (in with GCC and Clang do not apply the optimization).

The example in GCC's documentation for __may_alias__ also uses a typedef: https://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Type-Attributes.html

Pascal

__________________________
#include<string.h>

doubleX,Y;

voidf(void*d, constvoid*s) {
size_t __attribute__((__may_alias__)) *wd;
wd = d;
X = 1.0;
*wd = 1;
Y = X;
}

typedefsize_t __attribute__((__may_alias__)) aliasing_word;
voidg(void*d, constvoid*s) {
aliasing_word *wd;
wd = d;
X = 1.0;
*wd = 1;
Y = X;
}

Clang 6.0.0 -O3 -fomit-frame-pointer:
f:# @f
movabsq$4607182418800017408, %rax# imm = 0x3FF0000000000000
movq%rax, X(%rip)
movq$1, (%rdi)
movq%rax, Y(%rip)
retq
g:# @g
movabsq$4607182418800017408, %rax# imm = 0x3FF0000000000000
movq%rax, X(%rip)
movq$1, (%rdi)
movqX(%rip), %rax
movq%rax, Y(%rip)
retq

GCC 8.2 -O3 -fomit-frame-pointer:
f:
movsd.LC0(%rip), %xmm0
movsd%xmm0, X(%rip)
movq$1, (%rdi)
movsd%xmm0, Y(%rip)
ret
g:
movq.LC0(%rip), %rax
movq%rax, X(%rip)
movq$1, (%rdi)
movsdX(%rip), %xmm0
movsd%xmm0, Y(%rip)
ret
.LC0:
.long0
.long1072693248

[Rich Felker]

Post by Pascal Cuoq
Hello Rich,
I've had this patch sitting around since 2016, and just updated it to
apply cleanly. Any objections?
....
size_t __attribute__((__may_alias__)) *wd;
const size_t __attribute__((__may_alias__)) *ws;
....
In my experience, this use of __may_alias__ does not do anything.
See function f in the example below, which both GCC and Clang
https://gcc.godbolt.org/z/Um4NU7
You should use a typdef for the aliasing type, as shown for function
g (in with GCC and Clang do not apply the optimization).
The example in GCC's documentation for __may_alias__ also uses a
https://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Type-Attributes.html

Thanks, this is very helpful. I'll prepare an updated version.

Rich

[Rich Felker]

Post by Rich Felker

Post by Pascal Cuoq
Hello Rich,
I've had this patch sitting around since 2016, and just updated it to
apply cleanly. Any objections?
....
size_t __attribute__((__may_alias__)) *wd;
const size_t __attribute__((__may_alias__)) *ws;
....
In my experience, this use of __may_alias__ does not do anything.
See function f in the example below, which both GCC and Clang
https://gcc.godbolt.org/z/Um4NU7
You should use a typdef for the aliasing type, as shown for function
g (in with GCC and Clang do not apply the optimization).
The example in GCC's documentation for __may_alias__ also uses a
https://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Type-Attributes.html

Thanks, this is very helpful. I'll prepare an updated version.

While I've got your attention, I'm also trying to fix the UB in
address range checks for implementing memmove as memcpy, etc. Is this
correct:

if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n);

?

Rich

[Pascal Cuoq]

On 23 Sep 2018, at 04:45, Rich Felker <***@libc.org<mailto:***@libc.org>> wrote:
I'm also trying to fix the UB in
address range checks for implementing memmove as memcpy, etc. Is this
correct:

if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n);

?

It looks okay to me. You want to test whether (uintptr_t)s-(uintptr_t)d, computed as a mathematical integer, is between -n and n, and since uintptr_t is unsigned, you are using the well-known trick of aligning one of the bounds with 0 so that both inequalities can be tested in one instruction.

It would seen more natural to me to work on the right-hand side of zero, that it, to compute (uintptr_t)s-(uintptr_t)d+n and to check whether that is <= 2*n (overlap) or > 2*n (no overlap). The generated code may even be one instruction shorter. Apart from that, as long as we have the hypothesis that n <= UINTPTR_MAX/2, I cannot immediately see any reason why it would not work.

Pascal

[Rich Felker]

Post by Rich Felker
I'm also trying to fix the UB in
address range checks for implementing memmove as memcpy, etc. Is this
if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n);
?
It looks okay to me. You want to test whether
(uintptr_t)s-(uintptr_t)d, computed as a mathematical integer, is
between -n and n, and since uintptr_t is unsigned, you are using the
well-known trick of aligning one of the bounds with 0 so that both
inequalities can be tested in one instruction.

Right.

Post by Rich Felker
It would seen more natural to me to work on the right-hand side of
zero, that it, to compute (uintptr_t)s-(uintptr_t)d+n and to check
whether that is <= 2*n (overlap) or > 2*n (no overlap). The
generated code may even be one instruction shorter. Apart from that,
as long as we have the hypothesis that n <= UINTPTR_MAX/2, I cannot
immediately see any reason why it would not work.

dist(s,d)==n is a no-overlap case. Otherwise I think this is correct
and we can use:

if ((uintptr_t)s-(uintptr_t)d+n >= 2*n) return memcpy(d, s, n);

Yes?

Rich

[Pascal Cuoq]

Post by Rich Felker
dist(s,d)==n is a no-overlap case.
(uintptr_t)s-(uintptr_t)d-n <= -2*n

(uintptr_t)s-(uintptr_t)d = -n ==> comparison true by LHS and RHS being equal

(uintptr_t)s-(uintptr_t)d = n ==> comparison true by LHS being zero

(uintptr_t)s-(uintptr_t)d > -n and (uintptr_t)s-(uintptr_t)d < n ==> comparison false

[Rich Felker]

Post by Rich Felker
dist(s,d)==n is a no-overlap case.

In this case the formula I proposed has the drawback of rejecting
the case where (uintptr_t)s-(uintptr_t)d is exactly -n. This case
may be the justification for the way the original comparison was

I think that's fixable just by subtracting 1 on both sides, but then
it's probably less efficient rather than more efficient.

Post by Rich Felker
(uintptr_t)s-(uintptr_t)d-n <= -2*n

(uintptr_t)s-(uintptr_t)d = -n ==> comparison true by LHS and RHS being equal
(uintptr_t)s-(uintptr_t)d = n ==> comparison true by LHS being zero
(uintptr_t)s-(uintptr_t)d > -n and (uintptr_t)s-(uintptr_t)d < n ==> comparison false

Yes. It's interesting that the choice of using left or right of 0
depends on whether you want > or >=.

Rich

[Rich Felker]

Post by Rich Felker

Post by Rich Felker
I'm also trying to fix the UB in
address range checks for implementing memmove as memcpy, etc. Is this
if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n);
?
It looks okay to me. You want to test whether
(uintptr_t)s-(uintptr_t)d, computed as a mathematical integer, is
between -n and n, and since uintptr_t is unsigned, you are using the
well-known trick of aligning one of the bounds with 0 so that both
inequalities can be tested in one instruction.

Right.

Post by Rich Felker
It would seen more natural to me to work on the right-hand side of
zero, that it, to compute (uintptr_t)s-(uintptr_t)d+n and to check
whether that is <= 2*n (overlap) or > 2*n (no overlap). The
generated code may even be one instruction shorter. Apart from that,
as long as we have the hypothesis that n <= UINTPTR_MAX/2, I cannot
immediately see any reason why it would not work.

dist(s,d)==n is a no-overlap case. Otherwise I think this is correct
if ((uintptr_t)s-(uintptr_t)d+n >= 2*n) return memcpy(d, s, n);
Yes?

BTW just below there's a conditional if (d<s) that, as far as I can
tell, does not need any fixing. If we reach that point (if we don't
just call memcpy for the non-overlapping case) then, assuming n is
valid, d and s necessarily point into the same array, and therefore
d<s is well-defined.

Rich