Add new ABI '__memcmpeq()' to libc

Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

Hi All,

This is a proposal for a new interface to be supported by libc.

The new interface is the same as the old 'bcmp()' routine. Essentially
the goal of this proposal is to add a reserved namespace for a new
function, '__memcmpeq()', which shares the same behavior as the old
'bcmp()'.

#### Interface ####

int __memcmpeq(void const * s1, const void * s2, size_t n)


#### Description ####

The '__memcmpeq()' function would compare the two byte sequences 's1'
and 's2', each of length 'n'. If the two byte sequences are equal, the
return would be zero. Otherwise it would return some non-zero
value. 'memcmp()' is a valid implementation of '__memcmpeq()'.


#### Use Case ####

1. The goal is that '__memcmpeq()' will be usable as an optimization
   by compilers if a program uses the return value of 'memcmp()' as a
   boolean. For example:


void foo(const void* s1, const void* s2, size_t n)
{
    if (!memcmp(s1, s2, n)) {
        printf("memcmp can be optimized to __memcmpeq in this use case\n");
    }
}


- In the above case '__memcmpeq()' could be used instead. Due to the
  simpler constraints on the return value of '__memcmpeq()', it will
  be able to be implemented more optimally for this case than
  'memcmp()'. If there is no separately optimized version of
  '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
  fast.

2. Possibly use cases in security as the runtime of the function will
   be *more* oblivious to the byte sequences being compared.


#### Argument Specifications ####

1. 's1'
    - All 'n' bytes in the byte sequence starting at 's1' and ending
      at, but not including, 's1 + n' must be accessible memory. There
      are no guarantees about the order the sequence will be
      traversed.
2. 's2'
    - All 'n' bytes in the byte sequence starting at 's2' and ending
      at, but not including, 's2 + n' must be accessible memory. There
      are no guarantees about the order the sequence will be
      traversed.
3. 'n'
    - 'n' may be any value that does not violate the specifications on
      's1' and 's2'.

If any of the argument specifications are violated there are no
guarantees about the behavior of the interface.


#### Return Value Specification ####

If the byte sequences starting at 's1' and 's2' are equals the
function will return zero. Otherwise the function will return a
non-zero value.

Equality between the byte sequences starting at 's1' and 's2' is
defined as follows:

1. If 'n' is zero the two sequences are zero.
2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
   offset 'i' of 's1' equals the byte at offset 'i' in 's2'.

For a simple C implementation of '__memcmpeq()' could be as follows:


int __memcmpeq(const void* s1, const void* s2, size_t n)
{
    int ret;
    size_t i;
    const char *s1c, *s2c;
    s1c = (const char*)s1;
    s2c = (const char*)s2;
    for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
        ret = s1c[i] - s2c[i]
    }
    return ret;
}


#### Notes ####

This interface is essentially old 'bcmp()' and 'memcmp()' will always
be a valid implementation of '__memcmpeq()'.


#### ABI vs API ####

This proposal is for '__memcmpeq()' as a new ABI. As an ABI
'__memcmpeq()' will have value, as using the return value of
'memcmp()' is quite idiomatic in C code.

It is, however, possible that this would also be useful as a new API
as well. Especially if there are likely use cases where the compiler
would be unable to prove that '__memcmpeq()' would be a valid
replacement for 'memcmp()'.


#### Further Options ####

If this proposal is received positively, libc could also add
interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
which similarly would loosen return value restrictions on 'strcmp()',
'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.

Best,
Noah

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Chris Kennelly]

On Thu, Sep 16, 2021 at 1:04 PM Noah Goldstein <goldstein.w.n@gmail.com>
wrote:

> Hi All,
>
> This is a proposal for a new interface to be supported by libc.
>
> The new interface is the same as the old 'bcmp()' routine. Essentially
> the goal of this proposal is to add a reserved namespace for a new
> function, '__memcmpeq()', which shares the same behavior as the old
> 'bcmp()'.
>
> #### Interface ####
>
> int __memcmpeq(void const * s1, const void * s2, size_t n)
>
>
> #### Description ####
>
> The '__memcmpeq()' function would compare the two byte sequences 's1'
> and 's2', each of length 'n'. If the two byte sequences are equal, the
> return would be zero. Otherwise it would return some non-zero
> value. 'memcmp()' is a valid implementation of '__memcmpeq()'.
>
>
> #### Use Case ####
>
> 1. The goal is that '__memcmpeq()' will be usable as an optimization
>    by compilers if a program uses the return value of 'memcmp()' as a
>    boolean. For example:
>
>
> void foo(const void* s1, const void* s2, size_t n)
> {
>     if (!memcmp(s1, s2, n)) {
>         printf("memcmp can be optimized to __memcmpeq in this use case\n");
>     }
> }
>
>
> - In the above case '__memcmpeq()' could be used instead. Due to the
>   simpler constraints on the return value of '__memcmpeq()', it will
>   be able to be implemented more optimally for this case than
>   'memcmp()'. If there is no separately optimized version of
>   '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
>   fast.
>

LLVM does this transformation (but to bcmp), as part of
https://reviews.llvm.org/rG8e16d73346f8091461319a7dfc4ddd18eedcff13.  I
seem to recall a small amount of trickiness around determining whether the
platform had a bcmp.

Since this is intentionally the same as bcmp, is it possible to clarify the
motivation for additional symbol?


> 2. Possibly use cases in security as the runtime of the function will
>    be *more* oblivious to the byte sequences being compared.
>
>
> #### Argument Specifications ####
>
> 1. 's1'
>     - All 'n' bytes in the byte sequence starting at 's1' and ending
>       at, but not including, 's1 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 2. 's2'
>     - All 'n' bytes in the byte sequence starting at 's2' and ending
>       at, but not including, 's2 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 3. 'n'
>     - 'n' may be any value that does not violate the specifications on
>       's1' and 's2'.
>
> If any of the argument specifications are violated there are no
> guarantees about the behavior of the interface.
>
>
> #### Return Value Specification ####
>
> If the byte sequences starting at 's1' and 's2' are equals the
> function will return zero. Otherwise the function will return a
> non-zero value.
>
> Equality between the byte sequences starting at 's1' and 's2' is
> defined as follows:
>
> 1. If 'n' is zero the two sequences are zero.
> 2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
>    offset 'i' of 's1' equals the byte at offset 'i' in 's2'.
>
> For a simple C implementation of '__memcmpeq()' could be as follows:
>
>
> int __memcmpeq(const void* s1, const void* s2, size_t n)
> {
>     int ret;
>     size_t i;
>     const char *s1c, *s2c;
>     s1c = (const char*)s1;
>     s2c = (const char*)s2;
>     for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
>         ret = s1c[i] - s2c[i]
>     }
>     return ret;
> }
>
>
> #### Notes ####
>
> This interface is essentially old 'bcmp()' and 'memcmp()' will always
> be a valid implementation of '__memcmpeq()'.
>
>
> #### ABI vs API ####
>
> This proposal is for '__memcmpeq()' as a new ABI. As an ABI
> '__memcmpeq()' will have value, as using the return value of
> 'memcmp()' is quite idiomatic in C code.
>
> It is, however, possible that this would also be useful as a new API
> as well. Especially if there are likely use cases where the compiler
> would be unable to prove that '__memcmpeq()' would be a valid
> replacement for 'memcmp()'.
>
>
> #### Further Options ####
>
> If this proposal is received positively, libc could also add
> interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
> which similarly would loosen return value restrictions on 'strcmp()',
> 'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.
>
> Best,
> Noah
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Thu, Sep 16, 2021 at 12:55 PM Chris Kennelly via Libc-alpha <
libc-alpha@sourceware.org> wrote:

> On Thu, Sep 16, 2021 at 1:04 PM Noah Goldstein <goldstein.w.n@gmail.com>
> wrote:
>
> > Hi All,
> >
> > This is a proposal for a new interface to be supported by libc.
> >
> > The new interface is the same as the old 'bcmp()' routine. Essentially
> > the goal of this proposal is to add a reserved namespace for a new
> > function, '__memcmpeq()', which shares the same behavior as the old
> > 'bcmp()'.
> >
> > #### Interface ####
> >
> > int __memcmpeq(void const * s1, const void * s2, size_t n)
> >
> >
> > #### Description ####
> >
> > The '__memcmpeq()' function would compare the two byte sequences 's1'
> > and 's2', each of length 'n'. If the two byte sequences are equal, the
> > return would be zero. Otherwise it would return some non-zero
> > value. 'memcmp()' is a valid implementation of '__memcmpeq()'.
> >
> >
> > #### Use Case ####
> >
> > 1. The goal is that '__memcmpeq()' will be usable as an optimization
> >    by compilers if a program uses the return value of 'memcmp()' as a
> >    boolean. For example:
> >
> >
> > void foo(const void* s1, const void* s2, size_t n)
> > {
> >     if (!memcmp(s1, s2, n)) {
> >         printf("memcmp can be optimized to __memcmpeq in this use
> case\n");
> >     }
> > }
> >
> >
> > - In the above case '__memcmpeq()' could be used instead. Due to the
> >   simpler constraints on the return value of '__memcmpeq()', it will
> >   be able to be implemented more optimally for this case than
> >   'memcmp()'. If there is no separately optimized version of
> >   '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
> >   fast.
> >
>
> LLVM does this transformation (but to bcmp), as part of
> https://reviews.llvm.org/rG8e16d73346f8091461319a7dfc4ddd18eedcff13.  I
> seem to recall a small amount of trickiness around determining whether the
> platform had a bcmp.
>
> Since this is intentionally the same as bcmp, is it possible to clarify the
> motivation for additional symbol?
>

The motivation is to get a new reserved namespace for a function that
memcmp() calls can be transformed to if the return value is only used
for its boolean value.

I tried to add an optimized version of bcmp() to support LLVM's
transformation: https://patches-gcc.linaro.org/patch/60168/
But the consensus seems to be that bcmp() is not suitable because 1)
it is not a reserved namespace and 2) since it has had the same
functionality as memcmp() programs might have started relying on that
feature.

Do you want me to update the above proposal with this information or
were you just asking for more clarity for the thread?


>
>
> > 2. Possibly use cases in security as the runtime of the function will
> >    be *more* oblivious to the byte sequences being compared.
> >
> >
> > #### Argument Specifications ####
> >
> > 1. 's1'
> >     - All 'n' bytes in the byte sequence starting at 's1' and ending
> >       at, but not including, 's1 + n' must be accessible memory. There
> >       are no guarantees about the order the sequence will be
> >       traversed.
> > 2. 's2'
> >     - All 'n' bytes in the byte sequence starting at 's2' and ending
> >       at, but not including, 's2 + n' must be accessible memory. There
> >       are no guarantees about the order the sequence will be
> >       traversed.
> > 3. 'n'
> >     - 'n' may be any value that does not violate the specifications on
> >       's1' and 's2'.
> >
> > If any of the argument specifications are violated there are no
> > guarantees about the behavior of the interface.
> >
> >
> > #### Return Value Specification ####
> >
> > If the byte sequences starting at 's1' and 's2' are equals the
> > function will return zero. Otherwise the function will return a
> > non-zero value.
> >
> > Equality between the byte sequences starting at 's1' and 's2' is
> > defined as follows:
> >
> > 1. If 'n' is zero the two sequences are zero.
> > 2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
> >    offset 'i' of 's1' equals the byte at offset 'i' in 's2'.
> >
> > For a simple C implementation of '__memcmpeq()' could be as follows:
> >
> >
> > int __memcmpeq(const void* s1, const void* s2, size_t n)
> > {
> >     int ret;
> >     size_t i;
> >     const char *s1c, *s2c;
> >     s1c = (const char*)s1;
> >     s2c = (const char*)s2;
> >     for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
> >         ret = s1c[i] - s2c[i]
> >     }
> >     return ret;
> > }
> >
> >
> > #### Notes ####
> >
> > This interface is essentially old 'bcmp()' and 'memcmp()' will always
> > be a valid implementation of '__memcmpeq()'.
> >
> >
> > #### ABI vs API ####
> >
> > This proposal is for '__memcmpeq()' as a new ABI. As an ABI
> > '__memcmpeq()' will have value, as using the return value of
> > 'memcmp()' is quite idiomatic in C code.
> >
> > It is, however, possible that this would also be useful as a new API
> > as well. Especially if there are likely use cases where the compiler
> > would be unable to prove that '__memcmpeq()' would be a valid
> > replacement for 'memcmp()'.
> >
> >
> > #### Further Options ####
> >
> > If this proposal is received positively, libc could also add
> > interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
> > which similarly would loosen return value restrictions on 'strcmp()',
> > 'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.
> >
> > Best,
> > Noah
> >
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Chris Kennelly]

On Thu, Sep 16, 2021 at 2:31 PM Noah Goldstein <goldstein.w.n@gmail.com>
wrote:

>
>
> On Thu, Sep 16, 2021 at 12:55 PM Chris Kennelly via Libc-alpha <
> libc-alpha@sourceware.org> wrote:
>
>> On Thu, Sep 16, 2021 at 1:04 PM Noah Goldstein <goldstein.w.n@gmail.com>
>> wrote:
>>
>> > Hi All,
>> >
>> > This is a proposal for a new interface to be supported by libc.
>> >
>> > The new interface is the same as the old 'bcmp()' routine. Essentially
>> > the goal of this proposal is to add a reserved namespace for a new
>> > function, '__memcmpeq()', which shares the same behavior as the old
>> > 'bcmp()'.
>> >
>> > #### Interface ####
>> >
>> > int __memcmpeq(void const * s1, const void * s2, size_t n)
>> >
>> >
>> > #### Description ####
>> >
>> > The '__memcmpeq()' function would compare the two byte sequences 's1'
>> > and 's2', each of length 'n'. If the two byte sequences are equal, the
>> > return would be zero. Otherwise it would return some non-zero
>> > value. 'memcmp()' is a valid implementation of '__memcmpeq()'.
>> >
>> >
>> > #### Use Case ####
>> >
>> > 1. The goal is that '__memcmpeq()' will be usable as an optimization
>> >    by compilers if a program uses the return value of 'memcmp()' as a
>> >    boolean. For example:
>> >
>> >
>> > void foo(const void* s1, const void* s2, size_t n)
>> > {
>> >     if (!memcmp(s1, s2, n)) {
>> >         printf("memcmp can be optimized to __memcmpeq in this use
>> case\n");
>> >     }
>> > }
>> >
>> >
>> > - In the above case '__memcmpeq()' could be used instead. Due to the
>> >   simpler constraints on the return value of '__memcmpeq()', it will
>> >   be able to be implemented more optimally for this case than
>> >   'memcmp()'. If there is no separately optimized version of
>> >   '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
>> >   fast.
>> >
>>
>> LLVM does this transformation (but to bcmp), as part of
>> https://reviews.llvm.org/rG8e16d73346f8091461319a7dfc4ddd18eedcff13.  I
>> seem to recall a small amount of trickiness around determining whether the
>> platform had a bcmp.
>>
>> Since this is intentionally the same as bcmp, is it possible to clarify
>> the
>> motivation for additional symbol?
>>
>
> The motivation is to get a new reserved namespace for a function that
> memcmp() calls can be transformed to if the return value is only used
> for its boolean value.
>
> I tried to add an optimized version of bcmp() to support LLVM's
> transformation: https://patches-gcc.linaro.org/patch/60168/
> But the consensus seems to be that bcmp() is not suitable because 1)
> it is not a reserved namespace and 2) since it has had the same
> functionality as memcmp() programs might have started relying on that
> feature.
>

llvm-libc's bcmp differs from memcmp, but agreed that Hyrum's Law can cause
problems on point #2.

In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
simple alias for memcmp (since the notes mention that it's a valid
implementation), does that open up the possibility of depending on the
bcmp-like behavior that we were trying to escape?


>
> Do you want me to update the above proposal with this information or
> were you just asking for more clarity for the thread?
>
>
>>
>>
>> > 2. Possibly use cases in security as the runtime of the function will
>> >    be *more* oblivious to the byte sequences being compared.
>> >
>> >
>> > #### Argument Specifications ####
>> >
>> > 1. 's1'
>> >     - All 'n' bytes in the byte sequence starting at 's1' and ending
>> >       at, but not including, 's1 + n' must be accessible memory. There
>> >       are no guarantees about the order the sequence will be
>> >       traversed.
>> > 2. 's2'
>> >     - All 'n' bytes in the byte sequence starting at 's2' and ending
>> >       at, but not including, 's2 + n' must be accessible memory. There
>> >       are no guarantees about the order the sequence will be
>> >       traversed.
>> > 3. 'n'
>> >     - 'n' may be any value that does not violate the specifications on
>> >       's1' and 's2'.
>> >
>> > If any of the argument specifications are violated there are no
>> > guarantees about the behavior of the interface.
>> >
>> >
>> > #### Return Value Specification ####
>> >
>> > If the byte sequences starting at 's1' and 's2' are equals the
>> > function will return zero. Otherwise the function will return a
>> > non-zero value.
>> >
>> > Equality between the byte sequences starting at 's1' and 's2' is
>> > defined as follows:
>> >
>> > 1. If 'n' is zero the two sequences are zero.
>> > 2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
>> >    offset 'i' of 's1' equals the byte at offset 'i' in 's2'.
>> >
>> > For a simple C implementation of '__memcmpeq()' could be as follows:
>> >
>> >
>> > int __memcmpeq(const void* s1, const void* s2, size_t n)
>> > {
>> >     int ret;
>> >     size_t i;
>> >     const char *s1c, *s2c;
>> >     s1c = (const char*)s1;
>> >     s2c = (const char*)s2;
>> >     for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
>> >         ret = s1c[i] - s2c[i]
>> >     }
>> >     return ret;
>> > }
>> >
>> >
>> > #### Notes ####
>> >
>> > This interface is essentially old 'bcmp()' and 'memcmp()' will always
>> > be a valid implementation of '__memcmpeq()'.
>> >
>> >
>> > #### ABI vs API ####
>> >
>> > This proposal is for '__memcmpeq()' as a new ABI. As an ABI
>> > '__memcmpeq()' will have value, as using the return value of
>> > 'memcmp()' is quite idiomatic in C code.
>> >
>> > It is, however, possible that this would also be useful as a new API
>> > as well. Especially if there are likely use cases where the compiler
>> > would be unable to prove that '__memcmpeq()' would be a valid
>> > replacement for 'memcmp()'.
>> >
>> >
>> > #### Further Options ####
>> >
>> > If this proposal is received positively, libc could also add
>> > interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
>> > which similarly would loosen return value restrictions on 'strcmp()',
>> > 'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.
>> >
>> > Best,
>> > Noah
>> >
>>
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Joseph Myers]

On Thu, 16 Sep 2021, Chris Kennelly wrote:

> In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
> simple alias for memcmp (since the notes mention that it's a valid
> implementation), does that open up the possibility of depending on the
> bcmp-like behavior that we were trying to escape?

The proposal is as an ABI only (compilers would generate calls to 
__memcmpeq from boolean uses of memcmp, users wouldn't write calls to 
__memcmpeq directly, __memcmpeq wouldn't be declared in installed libc 
headers).  If such dependence arises, that would suggest a compiler bug 
wrongly generating such calls for non-boolean memcmp uses.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[enh]

(Android libc maintainer.)

should __memcmpeq be in compiler-rt rather than libc?

On Thu, Sep 16, 2021 at 1:35 PM Joseph Myers <joseph@codesourcery.com>
wrote:

> On Thu, 16 Sep 2021, Chris Kennelly wrote:
>
> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an
> a
> > simple alias for memcmp (since the notes mention that it's a valid
> > implementation), does that open up the possibility of depending on the
> > bcmp-like behavior that we were trying to escape?
>
> The proposal is as an ABI only (compilers would generate calls to
> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
> headers).  If such dependence arises, that would suggest a compiler bug
> wrongly generating such calls for non-boolean memcmp uses.
>
> --
> Joseph S. Myers
> joseph@codesourcery.com
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Richard Biener]

On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com> wrote:
>
> On Thu, 16 Sep 2021, Chris Kennelly wrote:
>
> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
> > simple alias for memcmp (since the notes mention that it's a valid
> > implementation), does that open up the possibility of depending on the
> > bcmp-like behavior that we were trying to escape?
>
> The proposal is as an ABI only (compilers would generate calls to
> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
> headers).  If such dependence arises, that would suggest a compiler bug
> wrongly generating such calls for non-boolean memcmp uses.

So the compiler would emit a call to __memcmpeq and at the same time
emit a weak alias of __memcmpeq to memcmp so the program links
when the libc version targeted does not provide __memcmpeq?  Or would
glibc through <string.h> magically communicate the availability of the new ABI
without actually declaring the function?
(I'm not sure whether a GCC build-time decision via configure is the
very best idea)

Richard.

> --
> Joseph S. Myers
> joseph@codesourcery.com

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Florian Weimer]

* Richard Biener via Gcc:

> On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com> wrote:
>>
>> On Thu, 16 Sep 2021, Chris Kennelly wrote:
>>
>> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
>> > simple alias for memcmp (since the notes mention that it's a valid
>> > implementation), does that open up the possibility of depending on the
>> > bcmp-like behavior that we were trying to escape?
>>
>> The proposal is as an ABI only (compilers would generate calls to
>> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
>> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
>> headers).  If such dependence arises, that would suggest a compiler bug
>> wrongly generating such calls for non-boolean memcmp uses.
>
> So the compiler would emit a call to __memcmpeq and at the same time
> emit a weak alias of __memcmpeq to memcmp so the program links
> when the libc version targeted does not provide __memcmpeq?  Or would
> glibc through <string.h> magically communicate the availability of the new ABI
> without actually declaring the function?

I do not think ELF provides that capability.

We can add a declaration to <string.h> to communicate the availability.
I think this is how glibc (and other libcs) communicate the availability
of non-standard interfaces to GCC.

> (I'm not sure whether a GCC build-time decision via configure is the
> very best idea)

If libstdc++ or libgcc_s have a symbol dependency on glibc 2.35 for
other (unrelated) reasons, would the build-time dependency be less of a
concern?  Because another such dependency exists?

Thanks,
Florian

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Richard Biener]

On Fri, Sep 17, 2021 at 10:08 AM Florian Weimer <fweimer@redhat.com> wrote:
>
> * Richard Biener via Gcc:
>
> > On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com> wrote:
> >>
> >> On Thu, 16 Sep 2021, Chris Kennelly wrote:
> >>
> >> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
> >> > simple alias for memcmp (since the notes mention that it's a valid
> >> > implementation), does that open up the possibility of depending on the
> >> > bcmp-like behavior that we were trying to escape?
> >>
> >> The proposal is as an ABI only (compilers would generate calls to
> >> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
> >> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
> >> headers).  If such dependence arises, that would suggest a compiler bug
> >> wrongly generating such calls for non-boolean memcmp uses.
> >
> > So the compiler would emit a call to __memcmpeq and at the same time
> > emit a weak alias of __memcmpeq to memcmp so the program links
> > when the libc version targeted does not provide __memcmpeq?  Or would
> > glibc through <string.h> magically communicate the availability of the new ABI
> > without actually declaring the function?
>
> I do not think ELF provides that capability.

I guess a weak forwarder should do the trick at the cost of a jmp.

> We can add a declaration to <string.h> to communicate the availability.
> I think this is how glibc (and other libcs) communicate the availability
> of non-standard interfaces to GCC.

OK, I guess that's fine.

> > (I'm not sure whether a GCC build-time decision via configure is the
> > very best idea)
>
> If libstdc++ or libgcc_s have a symbol dependency on glibc 2.35 for
> other (unrelated) reasons, would the build-time dependency be less of a
> concern?  Because another such dependency exists?

Not sure, I was thinking that we'd need to re-compile GCC when we
upgrade glibc to make use of the feature.

But then being able to run an executable on a system that does not
provide the ABI but a compatible one (memcmp) might be a nice
thing.

Richard.

> Thanks,
> Florian
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Florian Weimer]

* Richard Biener:

> On Fri, Sep 17, 2021 at 10:08 AM Florian Weimer <fweimer@redhat.com> wrote:
>>
>> * Richard Biener via Gcc:
>>
>> > On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com> wrote:
>> >>
>> >> On Thu, 16 Sep 2021, Chris Kennelly wrote:
>> >>
>> >> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
>> >> > simple alias for memcmp (since the notes mention that it's a valid
>> >> > implementation), does that open up the possibility of depending on the
>> >> > bcmp-like behavior that we were trying to escape?
>> >>
>> >> The proposal is as an ABI only (compilers would generate calls to
>> >> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
>> >> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
>> >> headers).  If such dependence arises, that would suggest a compiler bug
>> >> wrongly generating such calls for non-boolean memcmp uses.
>> >
>> > So the compiler would emit a call to __memcmpeq and at the same time
>> > emit a weak alias of __memcmpeq to memcmp so the program links
>> > when the libc version targeted does not provide __memcmpeq?  Or would
>> > glibc through <string.h> magically communicate the availability of the new ABI
>> > without actually declaring the function?
>>
>> I do not think ELF provides that capability.
>
> I guess a weak forwarder should do the trick at the cost of a jmp.

How would this look like in practice.

The GNU tools do not support weak symbol versions, so if you have a weak
reference to __memcmpeq@GLIBC_2.35, that's still a reference to the
GLIBC_2.35 symbol version.  The glibc 2.34 dynamic loader notes that
version and rejects the binary because GLIBC_2.35 does not exist.

(We should probably stop Cc:ing libc-coord because this is so very
GNU-specific at this point.)

Thanks,
Florian

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Richard Biener]

On Fri, Sep 17, 2021 at 10:37 AM Florian Weimer <fweimer@redhat.com> wrote:
>
> * Richard Biener:
>
> > On Fri, Sep 17, 2021 at 10:08 AM Florian Weimer <fweimer@redhat.com> wrote:
> >>
> >> * Richard Biener via Gcc:
> >>
> >> > On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com> wrote:
> >> >>
> >> >> On Thu, 16 Sep 2021, Chris Kennelly wrote:
> >> >>
> >> >> > In terms of relying on the feature:  If __memcmpeq is ever exposed as an a
> >> >> > simple alias for memcmp (since the notes mention that it's a valid
> >> >> > implementation), does that open up the possibility of depending on the
> >> >> > bcmp-like behavior that we were trying to escape?
> >> >>
> >> >> The proposal is as an ABI only (compilers would generate calls to
> >> >> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
> >> >> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
> >> >> headers).  If such dependence arises, that would suggest a compiler bug
> >> >> wrongly generating such calls for non-boolean memcmp uses.
> >> >
> >> > So the compiler would emit a call to __memcmpeq and at the same time
> >> > emit a weak alias of __memcmpeq to memcmp so the program links
> >> > when the libc version targeted does not provide __memcmpeq?  Or would
> >> > glibc through <string.h> magically communicate the availability of the new ABI
> >> > without actually declaring the function?
> >>
> >> I do not think ELF provides that capability.
> >
> > I guess a weak forwarder should do the trick at the cost of a jmp.
>
> How would this look like in practice.
>
> The GNU tools do not support weak symbol versions, so if you have a weak
> reference to __memcmpeq@GLIBC_2.35, that's still a reference to the
> GLIBC_2.35 symbol version.  The glibc 2.34 dynamic loader notes that
> version and rejects the binary because GLIBC_2.35 does not exist.

Aww, symbol versions. Yeah, that makes it difficult ...

Anyway, with a declaration available it's good enough I think.

Richard.

> (We should probably stop Cc:ing libc-coord because this is so very
> GNU-specific at this point.)
>
> Thanks,
> Florian
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Fri, Sep 17, 2021 at 3:32 AM Richard Biener via Gcc <gcc@gcc.gnu.org>
wrote:

> On Fri, Sep 17, 2021 at 10:08 AM Florian Weimer <fweimer@redhat.com>
> wrote:
> >
> > * Richard Biener via Gcc:
> >
> > > On Thu, Sep 16, 2021 at 10:36 PM Joseph Myers <joseph@codesourcery.com>
> wrote:
> > >>
> > >> On Thu, 16 Sep 2021, Chris Kennelly wrote:
> > >>
> > >> > In terms of relying on the feature:  If __memcmpeq is ever exposed
> as an a
> > >> > simple alias for memcmp (since the notes mention that it's a valid
> > >> > implementation), does that open up the possibility of depending on
> the
> > >> > bcmp-like behavior that we were trying to escape?
> > >>
> > >> The proposal is as an ABI only (compilers would generate calls to
> > >> __memcmpeq from boolean uses of memcmp, users wouldn't write calls to
> > >> __memcmpeq directly, __memcmpeq wouldn't be declared in installed libc
> > >> headers).  If such dependence arises, that would suggest a compiler
> bug
> > >> wrongly generating such calls for non-boolean memcmp uses.
> > >
> > > So the compiler would emit a call to __memcmpeq and at the same time
> > > emit a weak alias of __memcmpeq to memcmp so the program links
> > > when the libc version targeted does not provide __memcmpeq?  Or would
> > > glibc through <string.h> magically communicate the availability of the
> new ABI
> > > without actually declaring the function?
> >
> > I do not think ELF provides that capability.
>
> I guess a weak forwarder should do the trick at the cost of a jmp.
>

Where would the jmp be and under what conditions? Is there no way to achieve
this with zero overhead?


>
> > We can add a declaration to <string.h> to communicate the availability.
> > I think this is how glibc (and other libcs) communicate the availability
> > of non-standard interfaces to GCC.
>
> OK, I guess that's fine.
>
> > > (I'm not sure whether a GCC build-time decision via configure is the
> > > very best idea)
> >
> > If libstdc++ or libgcc_s have a symbol dependency on glibc 2.35 for
> > other (unrelated) reasons, would the build-time dependency be less of a
> > concern?  Because another such dependency exists?
>
> Not sure, I was thinking that we'd need to re-compile GCC when we
> upgrade glibc to make use of the feature.
>
> But then being able to run an executable on a system that does not
> provide the ABI but a compatible one (memcmp) might be a nice
> thing.
>
> Richard.
>
> > Thanks,
> > Florian
> >
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Jakub Jelinek]

On Fri, Sep 17, 2021 at 10:08:34AM +0200, Florian Weimer via Gcc wrote:
> > So the compiler would emit a call to __memcmpeq and at the same time
> > emit a weak alias of __memcmpeq to memcmp so the program links
> > when the libc version targeted does not provide __memcmpeq?  Or would
> > glibc through <string.h> magically communicate the availability of the new ABI
> > without actually declaring the function?
> 
> I do not think ELF provides that capability.
> 
> We can add a declaration to <string.h> to communicate the availability.
> I think this is how glibc (and other libcs) communicate the availability
> of non-standard interfaces to GCC.

Yeah, that is what we've done in the past, e.g. in case of stpcpy.

	Jakub

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Martin Sebor]

On 9/17/21 3:12 AM, Jakub Jelinek via Gcc wrote:
> On Fri, Sep 17, 2021 at 10:08:34AM +0200, Florian Weimer via Gcc wrote:
>>> So the compiler would emit a call to __memcmpeq and at the same time
>>> emit a weak alias of __memcmpeq to memcmp so the program links
>>> when the libc version targeted does not provide __memcmpeq?  Or would
>>> glibc through <string.h> magically communicate the availability of the new ABI
>>> without actually declaring the function?
>>
>> I do not think ELF provides that capability.
>>
>> We can add a declaration to <string.h> to communicate the availability.
>> I think this is how glibc (and other libcs) communicate the availability
>> of non-standard interfaces to GCC.
> 
> Yeah, that is what we've done in the past, e.g. in case of stpcpy.

The stpcpy hack has been a cause of mysterious bugs as discussed
in pr82429.  It means that programs that declare standard functions
without #including <string.h> or use GCC built-ins directly are
enalized by ending up with suboptimal code than those that do
include the header.

It's also a subtlety that not all of us keep in mind when working
on GCC, that can lead to wasted time trying to understand why
an expected optimization isn't working in one test case when it
does work in an apparently equivalent one.

Martin

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Joseph Myers]

On Fri, 17 Sep 2021, Richard Biener via Gcc wrote:

> when the libc version targeted does not provide __memcmpeq?  Or would
> glibc through <string.h> magically communicate the availability of the new ABI
> without actually declaring the function?
> (I'm not sure whether a GCC build-time decision via configure is the
> very best idea)

I was supposing a build-time decision (using GCC_GLIBC_VERSION_GTE_IFELSE 
to know if the glibc version on the target definitely has this function).  
But if we add a header declaration, you could check for __memcmpeq being 
declared (and so cover arbitrary C libraries, not just glibc, and avoid 
issues of needing to disable this logic for freestanding compilations, 
which would otherwise be an issue if a glibc-target toolchain is used for 
a freestanding kernel compilation).  The case of people calling 
__builtin_memcmp (or declaring memcmp themselves) without string.h 
included probably isn't one it's important to optimize.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Florian Weimer]

* Joseph Myers:

> I was supposing a build-time decision (using GCC_GLIBC_VERSION_GTE_IFELSE 
> to know if the glibc version on the target definitely has this function).  
> But if we add a header declaration, you could check for __memcmpeq being 
> declared (and so cover arbitrary C libraries, not just glibc, and avoid 
> issues of needing to disable this logic for freestanding compilations, 
> which would otherwise be an issue if a glibc-target toolchain is used for 
> a freestanding kernel compilation).  The case of people calling 
> __builtin_memcmp (or declaring memcmp themselves) without string.h 
> included probably isn't one it's important to optimize.

The header-less case looks relevant to C++ and other language front
ends, though.  So a GCC_GLIBC_VERSION_GTE_IFELSE check could still make
sense for them.

(Dropping libc-coord.)

Thanks,
Florian

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Fri, Sep 17, 2021 at 9:27 AM Florian Weimer via Libc-alpha <
libc-alpha@sourceware.org> wrote:

> * Joseph Myers:
>
> > I was supposing a build-time decision (using
> GCC_GLIBC_VERSION_GTE_IFELSE
> > to know if the glibc version on the target definitely has this
> function).
> > But if we add a header declaration, you could check for __memcmpeq being
> > declared (and so cover arbitrary C libraries, not just glibc, and avoid
> > issues of needing to disable this logic for freestanding compilations,
> > which would otherwise be an issue if a glibc-target toolchain is used
> for
> > a freestanding kernel compilation).  The case of people calling
> > __builtin_memcmp (or declaring memcmp themselves) without string.h
> > included probably isn't one it's important to optimize.
>
> The header-less case looks relevant to C++ and other language front
> ends, though.  So a GCC_GLIBC_VERSION_GTE_IFELSE check could still make
> sense for them.
>
> (Dropping libc-coord.)
>
> Thanks,
> Florian
>
>
What are we going with?

Should I go forward with the proposal in GLIBC?

If I should go forward with it should I include a def in string.h?

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Christoph Müllner]

Would it make sense to extend this proposal to include __strcmpeq()
and __strncmpeq()?

Both are already available internally in GCC in form of
BUILT_IN_STRCMP_EQ and BUILT_IN_STRNCMP_EQ
(tree-ssa-strlen.c detects them in handle_builtin_string_cmp() and
builtins.c tries to inline them in expand_builtin_memcmp()).
However, they are currently restricted to cases where the length of
the string or the size of the array (of both arguments) is known.

A use case for strcmpeq() would be the comparison of std::type_info
objects (equality and inequality operator) in libstdc++.

On Tue, Sep 21, 2021 at 9:54 PM Noah Goldstein via Gcc <gcc@gcc.gnu.org> wrote:
>
> On Fri, Sep 17, 2021 at 9:27 AM Florian Weimer via Libc-alpha <
> libc-alpha@sourceware.org> wrote:
>
> > * Joseph Myers:
> >
> > > I was supposing a build-time decision (using
> > GCC_GLIBC_VERSION_GTE_IFELSE
> > > to know if the glibc version on the target definitely has this
> > function).
> > > But if we add a header declaration, you could check for __memcmpeq being
> > > declared (and so cover arbitrary C libraries, not just glibc, and avoid
> > > issues of needing to disable this logic for freestanding compilations,
> > > which would otherwise be an issue if a glibc-target toolchain is used
> > for
> > > a freestanding kernel compilation).  The case of people calling
> > > __builtin_memcmp (or declaring memcmp themselves) without string.h
> > > included probably isn't one it's important to optimize.
> >
> > The header-less case looks relevant to C++ and other language front
> > ends, though.  So a GCC_GLIBC_VERSION_GTE_IFELSE check could still make
> > sense for them.
> >
> > (Dropping libc-coord.)
> >
> > Thanks,
> > Florian
> >
> >
> What are we going with?
>
> Should I go forward with the proposal in GLIBC?
>
> If I should go forward with it should I include a def in string.h?

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Wed, Sep 22, 2021 at 12:46 PM Christoph Müllner <cmuellner@gcc.gnu.org>
wrote:

> Would it make sense to extend this proposal to include __strcmpeq()
> and __strncmpeq()?
>
> Both are already available internally in GCC in form of
> BUILT_IN_STRCMP_EQ and BUILT_IN_STRNCMP_EQ
> (tree-ssa-strlen.c detects them in handle_builtin_string_cmp() and
> builtins.c tries to inline them in expand_builtin_memcmp()).
> However, they are currently restricted to cases where the length of
> the string or the size of the array (of both arguments) is known.
>
> A use case for strcmpeq() would be the comparison of std::type_info
> objects (equality and inequality operator) in libstdc++.
>
> I agree and am happy to implement them along side __memcmpeq()
if the proposal is accepted. Do they need a seperate writeup with full
specifications?


> On Tue, Sep 21, 2021 at 9:54 PM Noah Goldstein via Gcc <gcc@gcc.gnu.org>
> wrote:
> >
> > On Fri, Sep 17, 2021 at 9:27 AM Florian Weimer via Libc-alpha <
> > libc-alpha@sourceware.org> wrote:
> >
> > > * Joseph Myers:
> > >
> > > > I was supposing a build-time decision (using
> > > GCC_GLIBC_VERSION_GTE_IFELSE
> > > > to know if the glibc version on the target definitely has this
> > > function).
> > > > But if we add a header declaration, you could check for __memcmpeq
> being
> > > > declared (and so cover arbitrary C libraries, not just glibc, and
> avoid
> > > > issues of needing to disable this logic for freestanding
> compilations,
> > > > which would otherwise be an issue if a glibc-target toolchain is used
> > > for
> > > > a freestanding kernel compilation).  The case of people calling
> > > > __builtin_memcmp (or declaring memcmp themselves) without string.h
> > > > included probably isn't one it's important to optimize.
> > >
> > > The header-less case looks relevant to C++ and other language front
> > > ends, though.  So a GCC_GLIBC_VERSION_GTE_IFELSE check could still make
> > > sense for them.
> > >
> > > (Dropping libc-coord.)
> > >
> > > Thanks,
> > > Florian
> > >
> > >
> > What are we going with?
> >
> > Should I go forward with the proposal in GLIBC?
> >
> > If I should go forward with it should I include a def in string.h?
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[James Y Knight]

Wouldn't it be far simpler to just un-deprecate bcmp?

On Thu, Sep 16, 2021 at 1:04 PM Noah Goldstein <goldstein.w.n@gmail.com>
wrote:

> Hi All,
>
> This is a proposal for a new interface to be supported by libc.
>
> The new interface is the same as the old 'bcmp()' routine. Essentially
> the goal of this proposal is to add a reserved namespace for a new
> function, '__memcmpeq()', which shares the same behavior as the old
> 'bcmp()'.
>
> #### Interface ####
>
> int __memcmpeq(void const * s1, const void * s2, size_t n)
>
>
> #### Description ####
>
> The '__memcmpeq()' function would compare the two byte sequences 's1'
> and 's2', each of length 'n'. If the two byte sequences are equal, the
> return would be zero. Otherwise it would return some non-zero
> value. 'memcmp()' is a valid implementation of '__memcmpeq()'.
>
>
> #### Use Case ####
>
> 1. The goal is that '__memcmpeq()' will be usable as an optimization
>    by compilers if a program uses the return value of 'memcmp()' as a
>    boolean. For example:
>
>
> void foo(const void* s1, const void* s2, size_t n)
> {
>     if (!memcmp(s1, s2, n)) {
>         printf("memcmp can be optimized to __memcmpeq in this use case\n");
>     }
> }
>
>
> - In the above case '__memcmpeq()' could be used instead. Due to the
>   simpler constraints on the return value of '__memcmpeq()', it will
>   be able to be implemented more optimally for this case than
>   'memcmp()'. If there is no separately optimized version of
>   '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
>   fast.
>
> 2. Possibly use cases in security as the runtime of the function will
>    be *more* oblivious to the byte sequences being compared.
>
>
> #### Argument Specifications ####
>
> 1. 's1'
>     - All 'n' bytes in the byte sequence starting at 's1' and ending
>       at, but not including, 's1 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 2. 's2'
>     - All 'n' bytes in the byte sequence starting at 's2' and ending
>       at, but not including, 's2 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 3. 'n'
>     - 'n' may be any value that does not violate the specifications on
>       's1' and 's2'.
>
> If any of the argument specifications are violated there are no
> guarantees about the behavior of the interface.
>
>
> #### Return Value Specification ####
>
> If the byte sequences starting at 's1' and 's2' are equals the
> function will return zero. Otherwise the function will return a
> non-zero value.
>
> Equality between the byte sequences starting at 's1' and 's2' is
> defined as follows:
>
> 1. If 'n' is zero the two sequences are zero.
> 2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
>    offset 'i' of 's1' equals the byte at offset 'i' in 's2'.
>
> For a simple C implementation of '__memcmpeq()' could be as follows:
>
>
> int __memcmpeq(const void* s1, const void* s2, size_t n)
> {
>     int ret;
>     size_t i;
>     const char *s1c, *s2c;
>     s1c = (const char*)s1;
>     s2c = (const char*)s2;
>     for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
>         ret = s1c[i] - s2c[i]
>     }
>     return ret;
> }
>
>
> #### Notes ####
>
> This interface is essentially old 'bcmp()' and 'memcmp()' will always
> be a valid implementation of '__memcmpeq()'.
>
>
> #### ABI vs API ####
>
> This proposal is for '__memcmpeq()' as a new ABI. As an ABI
> '__memcmpeq()' will have value, as using the return value of
> 'memcmp()' is quite idiomatic in C code.
>
> It is, however, possible that this would also be useful as a new API
> as well. Especially if there are likely use cases where the compiler
> would be unable to prove that '__memcmpeq()' would be a valid
> replacement for 'memcmp()'.
>
>
> #### Further Options ####
>
> If this proposal is received positively, libc could also add
> interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
> which similarly would loosen return value restrictions on 'strcmp()',
> 'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.
>
> Best,
> Noah
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Joseph Myers]

On Thu, 16 Sep 2021, James Y Knight wrote:

> Wouldn't it be far simpler to just un-deprecate bcmp?

The aim is to have something to which calls can be generated in all 
standards modes.  bcmp has never been part of ISO C; there's nothing to 
undeprecate there.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[enh]

plus testing for _equality_ can (as mentioned earlier) have slightly
different properties from the three-way comparator behavior of
bcmp()/memcmp().

On Thu, Sep 16, 2021 at 2:43 PM Joseph Myers <joseph@codesourcery.com>
wrote:

> On Thu, 16 Sep 2021, James Y Knight wrote:
>
> > Wouldn't it be far simpler to just un-deprecate bcmp?
>
> The aim is to have something to which calls can be generated in all
> standards modes.  bcmp has never been part of ISO C; there's nothing to
> undeprecate there.
>
> --
> Joseph S. Myers
> joseph@codesourcery.com
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Thu, Sep 16, 2021, 4:50 PM enh via Libc-alpha <libc-alpha@sourceware.org>
wrote:

> plus testing for _equality_ can (as mentioned earlier) have slightly
> different properties from the three-way comparator behavior of
> bcmp()/memcmp().
>

How does bcmp() have a three-way comparator?

Or do you mean how it is currently implemented as an alias to memcmp()?


> On Thu, Sep 16, 2021 at 2:43 PM Joseph Myers <joseph@codesourcery.com>
> wrote:
>
> > On Thu, 16 Sep 2021, James Y Knight wrote:
> >
> > > Wouldn't it be far simpler to just un-deprecate bcmp?
> >
> > The aim is to have something to which calls can be generated in all
> > standards modes.  bcmp has never been part of ISO C; there's nothing to
> > undeprecate there.
> >
> > --
> > Joseph S. Myers
> > joseph@codesourcery.com
> >
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Chris Kennelly]

On Thu, Sep 16, 2021 at 5:50 PM enh <enh@google.com> wrote:

> plus testing for _equality_ can (as mentioned earlier) have slightly
> different properties from the three-way comparator behavior of
> bcmp()/memcmp().
>

llvm-libc's implementation only returns the boolean, though.

The mem* functions are extremely sensitive to instruction cache effects, so
having 3 unique implementations (__memcmpeq, bcmp, memcmp) that do similar,
but subtly different things can be a hidden performance cost--one that is
hard to demonstrate with a microbenchmark.  Our experience developing
optimized mem* routines ended up showing better performance in actual
applications when we accepted seemingly worse microbenchmark performance by
optimizing for code footprint instead (more extensive notes for mem* in
general
<https://storage.googleapis.com/pub-tools-public-publication-data/pdf/4f7c3da72d557ed418828823a8e59942859d677f.pdf>
and
memcmp specifically (section 4.4)
<https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf>
).

The alternative would be to alias (as the NOTES suggest as a possible
implementation), but I think that raises James' question of why not just
use bcmp?  Dependencies on non-boolean implementations of bcmp seem
rare--namely, I haven't actually seen one.


> On Thu, Sep 16, 2021 at 2:43 PM Joseph Myers <joseph@codesourcery.com>
> wrote:
>
>> On Thu, 16 Sep 2021, James Y Knight wrote:
>>
>> > Wouldn't it be far simpler to just un-deprecate bcmp?
>>
>> The aim is to have something to which calls can be generated in all
>> standards modes.  bcmp has never been part of ISO C; there's nothing to
>> undeprecate there.
>
>
>> --
>> Joseph S. Myers
>> joseph@codesourcery.com
>>
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Joseph Myers]

On Thu, 16 Sep 2021, Chris Kennelly wrote:

> The mem* functions are extremely sensitive to instruction cache effects, so
> having 3 unique implementations (__memcmpeq, bcmp, memcmp) that do similar,

I don't think anyone is suggesting 3 unique implementations.  The 
obsolescent name bcmp would be aliased to either __memcmpeq or memcmp 
(depending on whether there are concerns about existing binaries depending 
on bcmp acting like memcmp).  (And __memcmpeq and memcmp would be aliases 
on architectures without a separate optimized __memcmpeq.)

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Thu, Sep 16, 2021 at 5:25 PM Chris Kennelly via Libc-alpha <
libc-alpha@sourceware.org> wrote:

> On Thu, Sep 16, 2021 at 5:50 PM enh <enh@google.com> wrote:
>
> > plus testing for _equality_ can (as mentioned earlier) have slightly
> > different properties from the three-way comparator behavior of
> > bcmp()/memcmp().
> >
>
> llvm-libc's implementation only returns the boolean, though.
>
> The mem* functions are extremely sensitive to instruction cache effects, so
> having 3 unique implementations (__memcmpeq, bcmp, memcmp) that do similar,
> but subtly different things can be a hidden performance cost--one that is
> hard to demonstrate with a microbenchmark.  Our experience developing
> optimized mem* routines ended up showing better performance in actual
> applications when we accepted seemingly worse microbenchmark performance by
> optimizing for code footprint instead (more extensive notes for mem* in
> general
> <
> https://storage.googleapis.com/pub-tools-public-publication-data/pdf/4f7c3da72d557ed418828823a8e59942859d677f.pdf
> >
> and
> memcmp specifically (section 4.4)
> <
> https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf
> >
> ).
>

Regarding the code bloat found in memcmp in the paper, I think that is
pretty
exclusive to the sse4 implementation:

https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-sse4.S;h=b82adcd5fab5b60a0327819f6041a689a276916a;hb=HEAD

 And I think there is a fair argument to not include a __memcmpeq() based on
that implementation.

The older versions:
sse2:
https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/memcmp.S;h=870e15c5a080162b336b13bac24cf7afbac6874b;hb=HEAD
avx2:
https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-avx2-movbe.S;h=2621ec907aedb781fcf0444e831c801f18fa68ba;hb=HEAD
evex:
https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/multiarch/memcmp-evex-movbe.S;h=654dc7ac8ccb9445b2c7107a7cf2d9f6ce4b1010;hb=HEAD

Have a much more reasonable code size footprint.

Also the __memcmpeq() code will itself have a smaller code size footprint
that memcmp()

With the implementations from my patch the code size is shrunk the
following:
sse2: -66
avx2: -436
avx2: -500




> The alternative would be to alias (as the NOTES suggest as a possible
> implementation), but I think that raises James' question of why not just
> use bcmp?  Dependencies on non-boolean implementations of bcmp seem
> rare--namely, I haven't actually seen one.
>
>
> > On Thu, Sep 16, 2021 at 2:43 PM Joseph Myers <joseph@codesourcery.com>
> > wrote:
> >
> >> On Thu, 16 Sep 2021, James Y Knight wrote:
> >>
> >> > Wouldn't it be far simpler to just un-deprecate bcmp?
> >>
> >> The aim is to have something to which calls can be generated in all
> >> standards modes.  bcmp has never been part of ISO C; there's nothing to
> >> undeprecate there.
> >
> >
> >> --
> >> Joseph S. Myers
> >> joseph@codesourcery.com
> >>
> >
>

Re: [libc-coord] Add new ABI '__memcmpeq()' to libc

[James Y Knight]

On Thu, Sep 16, 2021 at 5:50 PM enh <enh@google.com> wrote:

> plus testing for _equality_ can (as mentioned earlier) have slightly
> different properties from the three-way comparator behavior of
> bcmp()/memcmp().
>

Per spec, bcmp is not a three-way comparison, it is an equality comparison
with exactly the same semantics as proposed for __memcmpeq.

Glibc currently implements bcmp as an alias to memcmp -- which is valid,
but provides more than just the boolean equality semantics. There was
concern raised that modifying that might break existing binaries. However,
this concern can be easily addressed in the same way glibc typically
addresses such compatibility concerns: creating a new symbol-version for
the new bcmp implementation, with the previous bcmp symbol-version
remaining as a memcmp alias.



> On Thu, Sep 16, 2021 at 2:43 PM Joseph Myers <joseph@codesourcery.com>
> wrote:
>
>> On Thu, 16 Sep 2021, James Y Knight wrote:
>>
>> > Wouldn't it be far simpler to just un-deprecate bcmp?
>>
>> The aim is to have something to which calls can be generated in all
>> standards modes.  bcmp has never been part of ISO C; there's nothing to
>> undeprecate there.
>
>
OK, I can see that. I suppose that strict ISO C compatibility could be
important to someone. :)

Re: Add new ABI '__memcmpeq()' to libc

[Noah Goldstein]

On Thu, Sep 16, 2021 at 12:02 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> Hi All,
>
> This is a proposal for a new interface to be supported by libc.
>
> The new interface is the same as the old 'bcmp()' routine. Essentially
> the goal of this proposal is to add a reserved namespace for a new
> function, '__memcmpeq()', which shares the same behavior as the old
> 'bcmp()'.
>
> #### Interface ####
>
> int __memcmpeq(void const * s1, const void * s2, size_t n)
>
>
> #### Description ####
>
> The '__memcmpeq()' function would compare the two byte sequences 's1'
> and 's2', each of length 'n'. If the two byte sequences are equal, the
> return would be zero. Otherwise it would return some non-zero
> value. 'memcmp()' is a valid implementation of '__memcmpeq()'.
>
>
> #### Use Case ####
>
> 1. The goal is that '__memcmpeq()' will be usable as an optimization
>    by compilers if a program uses the return value of 'memcmp()' as a
>    boolean. For example:
>
>
> void foo(const void* s1, const void* s2, size_t n)
> {
>     if (!memcmp(s1, s2, n)) {
>         printf("memcmp can be optimized to __memcmpeq in this use case\n");
>     }
> }
>
>
> - In the above case '__memcmpeq()' could be used instead. Due to the
>   simpler constraints on the return value of '__memcmpeq()', it will
>   be able to be implemented more optimally for this case than
>   'memcmp()'. If there is no separately optimized version of
>   '__memcmpeq()' can alias 'memcmp()' and thus be at least equally as
>   fast.
>
> 2. Possibly use cases in security as the runtime of the function will
>    be *more* oblivious to the byte sequences being compared.
>
>
> #### Argument Specifications ####
>
> 1. 's1'
>     - All 'n' bytes in the byte sequence starting at 's1' and ending
>       at, but not including, 's1 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 2. 's2'
>     - All 'n' bytes in the byte sequence starting at 's2' and ending
>       at, but not including, 's2 + n' must be accessible memory. There
>       are no guarantees about the order the sequence will be
>       traversed.
> 3. 'n'
>     - 'n' may be any value that does not violate the specifications on
>       's1' and 's2'.
>
> If any of the argument specifications are violated there are no
> guarantees about the behavior of the interface.
>
>
> #### Return Value Specification ####
>
> If the byte sequences starting at 's1' and 's2' are equals the
> function will return zero. Otherwise the function will return a
> non-zero value.
>
> Equality between the byte sequences starting at 's1' and 's2' is
> defined as follows:
>
> 1. If 'n' is zero the two sequences are zero.
> 2. If 'n' is non-zero then for all 'i' in range [0, n) the byte at
>    offset 'i' of 's1' equals the byte at offset 'i' in 's2'.
>
> For a simple C implementation of '__memcmpeq()' could be as follows:
>
>
> int __memcmpeq(const void* s1, const void* s2, size_t n)
> {
>     int ret;
>     size_t i;
>     const char *s1c, *s2c;
>     s1c = (const char*)s1;
>     s2c = (const char*)s2;
>     for (i = 0, ret = 0; ret == 0 && i < n; ++i) {
>         ret = s1c[i] - s2c[i]
>     }
>     return ret;
> }
>
>
> #### Notes ####
>
> This interface is essentially old 'bcmp()' and 'memcmp()' will always
> be a valid implementation of '__memcmpeq()'.
>
>
> #### ABI vs API ####
>
> This proposal is for '__memcmpeq()' as a new ABI. As an ABI
> '__memcmpeq()' will have value, as using the return value of
> 'memcmp()' is quite idiomatic in C code.
>
> It is, however, possible that this would also be useful as a new API
> as well. Especially if there are likely use cases where the compiler
> would be unable to prove that '__memcmpeq()' would be a valid
> replacement for 'memcmp()'.
>
>
> #### Further Options ####
>
> If this proposal is received positively, libc could also add
> interfaces for '__streq()', '__strneq()', '__wcseq()' and '__wcsneq()'
> which similarly would loosen return value restrictions on 'strcmp()',
> 'strncmp()', 'wcscmp()' and 'wcsncmp()' respectively.
>
> Best,
> Noah

ABI support for '__memcmpeq' have been pushed for GLIBC with:
commit 44829b3ddb64e99e37343a0f25b2c082387d31a5