libc-coord - Add new ABI '__memcmpeq()' to libc

Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAFUsyfJLcDuUhF+97u9DNMR8+u0WEHdVEtaDLLmG_6dLU-6DuA@mail.gmail.com>
Date: Thu, 16 Sep 2021 12:02:02 -0500
From: Noah Goldstein <goldstein.w.n@...il.com>
To: libc-coord@...ts.openwall.com
Cc: GNU C Library <libc-alpha@...rceware.org>, gcc@....gnu.org
Subject: Add new ABI '__memcmpeq()' to libc

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

Content of type "text/html" skipped
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.