[musl] [C23 new stdlib 0/4] changes in stdlib.h

[musl] [C23 new stdlib 0/4] changes in stdlib.h

[Jens Gustedt]

In C23, <stdlib.h> comes with a handful of new functions

Jens Gustedt (4):
  C23: add the new interfaces free_sized and free_aligned_sized for
    stdlib.h
  C23: add the memalignment function
  C23: implement the new strfrom[dfl] functions
  C23: add the new include guard to stdlib.h

 include/stdlib.h          | 13 +++++++++++--
 src/malloc/free.c         | 10 ++++++++++
 src/stdlib/memalignment.c |  6 ++++++
 src/stdlib/strfromd.c     | 21 +++++++++++++++++++++
 4 files changed, 48 insertions(+), 2 deletions(-)
 create mode 100644 src/stdlib/memalignment.c
 create mode 100644 src/stdlib/strfromd.c

-- 
2.34.1

[musl] [C23 new stdlib 1/4] C23: add the new interfaces free_sized and free_aligned_sized for stdlib.h

[Jens Gustedt]

For the moment, these are just trivial wrappers that ignored their
parameters other than the pointer.

The names were not previously reserved, so they could generate naming
conflicts with application code.

The "implementation" is just a trivial wrapper around free. This could
eventually replaced by implementations that are more efficient than
that.
---
 include/stdlib.h  |  2 ++
 src/malloc/free.c | 10 ++++++++++
 2 files changed, 12 insertions(+)

diff --git a/include/stdlib.h b/include/stdlib.h
index 8a873f03..7800074d 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -41,6 +41,8 @@ void *malloc (size_t);
 void *calloc (size_t, size_t);
 void *realloc (void *, size_t);
 void free (void *);
+void free_sized (void *, size_t);
+void free_aligned_sized (void *, size_t, size_t);
 void *aligned_alloc(size_t, size_t);
 
 __noreturn void abort (void);
diff --git a/src/malloc/free.c b/src/malloc/free.c
index 3944f7b2..2b7438bc 100644
--- a/src/malloc/free.c
+++ b/src/malloc/free.c
@@ -4,3 +4,13 @@ void free(void *p)
 {
 	__libc_free(p);
 }
+
+void free_sized (void *p, size_t size)
+{
+	__libc_free(p);
+}
+
+void free_aligned_sized (void *p, size_t alignment, size_t size)
+{
+	__libc_free(p);
+}
-- 
2.34.1

[musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jens Gustedt]

The name is reserved, so we don't need to protect it via a feature
macro or a weak symbol.
---
 include/stdlib.h          | 3 +++
 src/stdlib/memalignment.c | 6 ++++++
 2 files changed, 9 insertions(+)
 create mode 100644 src/stdlib/memalignment.c

diff --git a/include/stdlib.h b/include/stdlib.h
index 7800074d..68993c04 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -178,6 +178,9 @@ long double strtold_l(const char *__restrict, char **__restrict, struct __locale
 typedef int once_flag;
 void call_once(once_flag *, void (*)(void));
 
+size_t (memalignment)(const void *);
+#define memalignment(P) (((size_t)1)<<__builtin_ctzll((unsigned long long)P))
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/src/stdlib/memalignment.c b/src/stdlib/memalignment.c
new file mode 100644
index 00000000..58b68954
--- /dev/null
+++ b/src/stdlib/memalignment.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+size_t (memalignment)(const void *p)
+{
+	return memalignment(p);
+}
-- 
2.34.1

[musl] [C23 new stdlib 3/4] C23: implement the new strfrom[dfl] functions

[Jens Gustedt]

These names had been reserved in C17, so it is not necessary to hide
these function in conditionals or to make the symbols weak.
---
 include/stdlib.h      |  4 ++++
 src/stdlib/strfromd.c | 21 +++++++++++++++++++++
 2 files changed, 25 insertions(+)
 create mode 100644 src/stdlib/strfromd.c

diff --git a/include/stdlib.h b/include/stdlib.h
index 68993c04..43173e95 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -29,6 +29,10 @@ float strtof (const char *__restrict, char **__restrict);
 double strtod (const char *__restrict, char **__restrict);
 long double strtold (const char *__restrict, char **__restrict);
 
+int strfromd(char *restrict, size_t, const char *restrict, double);
+int strfromf(char *restrict, size_t, const char *restrict, float);
+int strfroml(char *restrict, size_t, const char *restrict, long double);
+
 long strtol (const char *__restrict, char **__restrict, int);
 unsigned long strtoul (const char *__restrict, char **__restrict, int);
 long long strtoll (const char *__restrict, char **__restrict, int);
diff --git a/src/stdlib/strfromd.c b/src/stdlib/strfromd.c
new file mode 100644
index 00000000..c04a1d82
--- /dev/null
+++ b/src/stdlib/strfromd.c
@@ -0,0 +1,21 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+int strfromd(char *restrict s, size_t n, const char *restrict format, double fp) {
+	return snprintf(s, n, format, fp);
+}
+
+int strfromf(char *restrict s, size_t n, const char *restrict format, float fp) {
+	return snprintf(s, n, format, fp);
+}
+
+int strfroml(char *restrict s, size_t n, const char *restrict format, long double fp) {
+	size_t len = strlen(format);
+	char ff[len+2];
+	memcpy(ff, format, len-1);
+	ff[len-1] = 'L';
+	ff[len] = format[len-1];
+	ff[len+1] = 0;
+	return snprintf(s, n, ff, fp);
+}
-- 
2.34.1

[musl] [C23 new stdlib 4/4] C23: add the new include guard to stdlib.h

[Jens Gustedt]

---
 include/stdlib.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/stdlib.h b/include/stdlib.h
index 43173e95..68ccd467 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -1,5 +1,5 @@
-#ifndef _STDLIB_H
-#define _STDLIB_H
+#ifndef __STDC_VERSION_STDLIB_H__
+#define __STDC_VERSION_STDLIB_H__ 202304L
 
 #ifdef __cplusplus
 extern "C" {
-- 
2.34.1

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Rich Felker]

On Wed, May 24, 2023 at 09:38:52PM +0200, Jens Gustedt wrote:
> The name is reserved, so we don't need to protect it via a feature
> macro or a weak symbol.
> ---
>  include/stdlib.h          | 3 +++
>  src/stdlib/memalignment.c | 6 ++++++
>  2 files changed, 9 insertions(+)
>  create mode 100644 src/stdlib/memalignment.c
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index 7800074d..68993c04 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -178,6 +178,9 @@ long double strtold_l(const char *__restrict, char **__restrict, struct __locale
>  typedef int once_flag;
>  void call_once(once_flag *, void (*)(void));
>  
> +size_t (memalignment)(const void *);
> +#define memalignment(P) (((size_t)1)<<__builtin_ctzll((unsigned long long)P))
> +
>  #ifdef __cplusplus
>  }
>  #endif
> diff --git a/src/stdlib/memalignment.c b/src/stdlib/memalignment.c
> new file mode 100644
> index 00000000..58b68954
> --- /dev/null
> +++ b/src/stdlib/memalignment.c
> @@ -0,0 +1,6 @@
> +#include <stdlib.h>
> +
> +size_t (memalignment)(const void *p)
> +{
> +	return memalignment(p);
> +}
> -- 
> 2.34.1

There's a more efficient implementation of this function which does
not depend on __builtin_ctzll (which we don't): p^(p-1)&p

I'm not clear that there's a really good motivation for having it
implemented in the header. It kinda falls under the "maybe do it
because it's easy" case, but once you switch to the non-GNUC-specific
version, it needs a static inline function to avoid multiple
evaluation, and then it gets to the point of "this is really too much
code to have in a header" (which is more an issue of avoiding
"creative" content in headers than anything else).

Rich

Re: [musl] [C23 new stdlib 1/4] C23: add the new interfaces free_sized and free_aligned_sized for stdlib.h

[Rich Felker]

On Wed, May 24, 2023 at 09:38:51PM +0200, Jens Gustedt wrote:
> For the moment, these are just trivial wrappers that ignored their
> parameters other than the pointer.
> 
> The names were not previously reserved, so they could generate naming
> conflicts with application code.
> 
> The "implementation" is just a trivial wrapper around free. This could
> eventually replaced by implementations that are more efficient than
> that.
> ---
>  include/stdlib.h  |  2 ++
>  src/malloc/free.c | 10 ++++++++++
>  2 files changed, 12 insertions(+)
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index 8a873f03..7800074d 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -41,6 +41,8 @@ void *malloc (size_t);
>  void *calloc (size_t, size_t);
>  void *realloc (void *, size_t);
>  void free (void *);
> +void free_sized (void *, size_t);
> +void free_aligned_sized (void *, size_t, size_t);
>  void *aligned_alloc(size_t, size_t);
>  
>  __noreturn void abort (void);
> diff --git a/src/malloc/free.c b/src/malloc/free.c
> index 3944f7b2..2b7438bc 100644
> --- a/src/malloc/free.c
> +++ b/src/malloc/free.c
> @@ -4,3 +4,13 @@ void free(void *p)
>  {
>  	__libc_free(p);
>  }
> +
> +void free_sized (void *p, size_t size)
> +{
> +	__libc_free(p);
> +}
> +
> +void free_aligned_sized (void *p, size_t alignment, size_t size)
> +{
> +	__libc_free(p);
> +}
> -- 
> 2.34.1

These really should be in a separate file or files calling free() not
__libc_free, since if free has been replaced, they should call that,
not the libc-internal one. (Imagine a program linked or LD_PRELOADed
with an alternate malloc implementation that's not C23-aware.)

Optionally, they could also evaluate the predicate to determine if
malloc has been replaced, and if not, do the actual check. The
alignment check is trivial and malloc-agnostic. The size check would
require adding a libc-internal way to access malloc_usable_size. But
this can all be done later if desired.

Rich

Re: [musl] [C23 new stdlib 3/4] C23: implement the new strfrom[dfl] functions

[Rich Felker]

On Wed, May 24, 2023 at 09:38:53PM +0200, Jens Gustedt wrote:
> These names had been reserved in C17, so it is not necessary to hide
> these function in conditionals or to make the symbols weak.
> ---
>  include/stdlib.h      |  4 ++++
>  src/stdlib/strfromd.c | 21 +++++++++++++++++++++
>  2 files changed, 25 insertions(+)
>  create mode 100644 src/stdlib/strfromd.c
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index 68993c04..43173e95 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -29,6 +29,10 @@ float strtof (const char *__restrict, char **__restrict);
>  double strtod (const char *__restrict, char **__restrict);
>  long double strtold (const char *__restrict, char **__restrict);
>  
> +int strfromd(char *restrict, size_t, const char *restrict, double);
> +int strfromf(char *restrict, size_t, const char *restrict, float);
> +int strfroml(char *restrict, size_t, const char *restrict, long double);
> +
>  long strtol (const char *__restrict, char **__restrict, int);
>  unsigned long strtoul (const char *__restrict, char **__restrict, int);
>  long long strtoll (const char *__restrict, char **__restrict, int);
> diff --git a/src/stdlib/strfromd.c b/src/stdlib/strfromd.c
> new file mode 100644
> index 00000000..c04a1d82
> --- /dev/null
> +++ b/src/stdlib/strfromd.c
> @@ -0,0 +1,21 @@
> +#include <stdlib.h>
> +#include <stdio.h>
> +#include <string.h>
> +
> +int strfromd(char *restrict s, size_t n, const char *restrict format, double fp) {
> +	return snprintf(s, n, format, fp);
> +}
> +
> +int strfromf(char *restrict s, size_t n, const char *restrict format, float fp) {
> +	return snprintf(s, n, format, fp);
> +}
> +
> +int strfroml(char *restrict s, size_t n, const char *restrict format, long double fp) {
> +	size_t len = strlen(format);
> +	char ff[len+2];
> +	memcpy(ff, format, len-1);
> +	ff[len-1] = 'L';
> +	ff[len] = format[len-1];
> +	ff[len+1] = 0;
> +	return snprintf(s, n, ff, fp);
> +}
> -- 
> 2.34.1

The temp buffer of unbounded length is kinda a problem here,
especially if they might be used with untrusted input. This is kinda
sketchy to begin with since, AIUI, the "shall only..." language in the
spec makes it UB to pass a format that's not valid, but one could
imagine a program correctly validating formats with a regex like
/%([.][0-9]*)?[aAeEfFgG]/ but not imposing a length limit.

The safe thing to do would probably be stripping leading zeros and
then substituting "9999999999" or something if there are more than 10
digits remaining. For width (not supported here) this would
necessarily cause EOVERFLOW, but for precision, it might not. In any
case, then the entire format fits in a small fixed-length buffer and
has no risk of stack smashing.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Rich Felker]

On Wed, May 24, 2023 at 05:28:35PM -0400, Rich Felker wrote:
> On Wed, May 24, 2023 at 09:38:52PM +0200, Jens Gustedt wrote:
> > The name is reserved, so we don't need to protect it via a feature
> > macro or a weak symbol.
> > ---
> >  include/stdlib.h          | 3 +++
> >  src/stdlib/memalignment.c | 6 ++++++
> >  2 files changed, 9 insertions(+)
> >  create mode 100644 src/stdlib/memalignment.c
> > 
> > diff --git a/include/stdlib.h b/include/stdlib.h
> > index 7800074d..68993c04 100644
> > --- a/include/stdlib.h
> > +++ b/include/stdlib.h
> > @@ -178,6 +178,9 @@ long double strtold_l(const char *__restrict, char **__restrict, struct __locale
> >  typedef int once_flag;
> >  void call_once(once_flag *, void (*)(void));
> >  
> > +size_t (memalignment)(const void *);
> > +#define memalignment(P) (((size_t)1)<<__builtin_ctzll((unsigned long long)P))
> > +
> >  #ifdef __cplusplus
> >  }
> >  #endif
> > diff --git a/src/stdlib/memalignment.c b/src/stdlib/memalignment.c
> > new file mode 100644
> > index 00000000..58b68954
> > --- /dev/null
> > +++ b/src/stdlib/memalignment.c
> > @@ -0,0 +1,6 @@
> > +#include <stdlib.h>
> > +
> > +size_t (memalignment)(const void *p)
> > +{
> > +	return memalignment(p);
> > +}
> > -- 
> > 2.34.1
> 
> There's a more efficient implementation of this function which does
> not depend on __builtin_ctzll (which we don't): p^(p-1)&p
> 
> I'm not clear that there's a really good motivation for having it
> implemented in the header. It kinda falls under the "maybe do it
> because it's easy" case, but once you switch to the non-GNUC-specific
> version, it needs a static inline function to avoid multiple
> evaluation, and then it gets to the point of "this is really too much
> code to have in a header" (which is more an issue of avoiding
> "creative" content in headers than anything else).

I was reading the spec and came across:

    "If p is a null pointer, an alignment of zero is returned."

and:

    "NOTE An alignment of zero indicates that the tested pointer
    cannot be used to access an object of any type."

I think this precludes your version with ctzll, but works fine with
the replacement I proposed.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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

Rich,

on Wed, 24 May 2023 17:28:35 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> There's a more efficient implementation of this function which does
> not depend on __builtin_ctzll (which we don't): p^(p-1)&p

yes, nice

If you have other such nice formulas for some of the interfaces in
<stdbit.h>, please let me know. They are hard to find in search
engines.

For `__builtin_ctzll`, hm, I counted also to use these for the
<stdbit.h> interfaces. I think the intent of those is really to
provide instruction level support of these bit functionalities that
avoids going through function calls.

I see that we use other quite specific builtins, such as
`__builtin_fma`. Is there a particular reason not to have the bit
level ones?

So you want me to use the ctz and clz interfaces from the internal
atomics for the implementation of <stdbit.h>? Are they not overkill
for this simple purpose? (I mean they are meant to be atomic, arent't
they?)

> I'm not clear that there's a really good motivation for having it
> implemented in the header. It kinda falls under the "maybe do it
> because it's easy" case, but once you switch to the non-GNUC-specific
> version, it needs a static inline function to avoid multiple
> evaluation,

I guess using `({ ... })` would also not be acceptable?

> and then it gets to the point of "this is really too much
> code to have in a header" (which is more an issue of avoiding
> "creative" content in headers than anything else).

You probably won't like what I have now for the bit operations, then
:-(


Thanks
Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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


on Wed, 24 May 2023 18:12:05 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> I was reading the spec and came across:
> 
>     "If p is a null pointer, an alignment of zero is returned."
> 
> and:
> 
>     "NOTE An alignment of zero indicates that the tested pointer
>     cannot be used to access an object of any type."
> 
> I think this precludes your version with ctzll, but works fine with
> the replacement I proposed.

good catch


Thanks
Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 1/4] C23: add the new interfaces free_sized and free_aligned_sized for stdlib.h

[Jₑₙₛ Gustedt]

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


on Wed, 24 May 2023 17:31:34 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> These really should be in a separate file or files calling free() not
> __libc_free, since if free has been replaced, they should call that,
> not the libc-internal one. (Imagine a program linked or LD_PRELOADed
> with an alternate malloc implementation that's not C23-aware.)

ok

> Optionally, they could also evaluate the predicate to determine if
> malloc has been replaced, and if not, do the actual check. The
> alignment check is trivial and malloc-agnostic. The size check would
> require adding a libc-internal way to access malloc_usable_size. But
> this can all be done later if desired.

I don't think these interfaces are about checking consistency. They
don't provide any reasonable means to return an error. In the contrary
they are meant to provide more efficient implementations for the
feature if the correct size is used. Otherwise, the behavior is just
undefined.

The first question to be would be if we want to offer that
functionality for musl's allocator. (I don't feel that I know enough
to do that.) The second question is, do we want to allow alternate
malloc implementations to provide replacements for this? Then we
should perhaps have these new interfaces as weak symbols?

Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[NRK]

On Thu, May 25, 2023 at 11:16:53AM +0200, Jₑₙₛ Gustedt wrote:
> I think the intent of those is really to provide instruction level
> support of these bit functionalities that avoids going through
> function calls.

That doesn't really have to be done at the libc level, though. If the
interface is standardized, then compilers can assume their behavior and
substitute in suitable instruction if it feels like it.

For example, both gcc and clang are capable of turning the following
into a single mov instruction on amd64:

	void f(void *p, long n) { memcpy(p, &n, sizeof n); }

Compile with `gcc -O2 -S test.c` and inspect the asm (I've removed some
noise from the output):

	f:
		movq	%rsi, (%rdi)
		ret

As such, I don't think it's necessary to implement these in the headers.
Compilers that already support `__builtin_*` bit functions can be tuned
to understand the C23 bit functions as well.

- NRK

Re: [musl] [C23 new stdlib 1/4] C23: add the new interfaces free_sized and free_aligned_sized for stdlib.h

[Rich Felker]

On Thu, May 25, 2023 at 11:38:06AM +0200, Jₑₙₛ Gustedt wrote:
> 
> on Wed, 24 May 2023 17:31:34 -0400 you (Rich Felker <dalias@libc.org>)
> wrote:
> 
> > These really should be in a separate file or files calling free() not
> > __libc_free, since if free has been replaced, they should call that,
> > not the libc-internal one. (Imagine a program linked or LD_PRELOADed
> > with an alternate malloc implementation that's not C23-aware.)
> 
> ok
> 
> > Optionally, they could also evaluate the predicate to determine if
> > malloc has been replaced, and if not, do the actual check. The
> > alignment check is trivial and malloc-agnostic. The size check would
> > require adding a libc-internal way to access malloc_usable_size. But
> > this can all be done later if desired.
> 
> I don't think these interfaces are about checking consistency. They
> don't provide any reasonable means to return an error. In the contrary
> they are meant to provide more efficient implementations for the
> feature if the correct size is used. Otherwise, the behavior is just
> undefined.

My understanding was that, by having it be UB to call them with wrong
size or alignment, they create an opportunity for the implementation
to harden by trapping on inconsistency. This is a lot more valuable
than whatever marginal performance advantage they might give (which is
none for musl's mallocng or oldmalloc, anyway).

> The first question to be would be if we want to offer that
> functionality for musl's allocator. (I don't feel that I know enough
> to do that.) The second question is, do we want to allow alternate
> malloc implementations to provide replacements for this? Then we
> should perhaps have these new interfaces as weak symbols?

Weak symbols aren't the way to achieve that. They might be ~a way~ in
some cases, but probably not a good one. What we use weak symbols for
in musl is to allow stub implementations for the pattern "B needs to
do something to interact with A if A was linked, but can skip that if
A was not linked" without having B pull in A as a dependency.

For static linking, just having the functions in separate TUs
automatically gives the property of being able to provide a
replacement (but there also has to be a contract to allow replacement;
the malloc subsystem is the only thing for which we have such a
contract, as an extension).

For dynamic linking, weak is irrelevant/ignored, and interposition (by
design) approximates the static linking behavior. Since redefining
standard functions is UB, we link with most symbol references inside
libc.so bound at libc.so link time, so that calls don't have to go
through GOT lookup or PLT. But for malloc, we suppress that via the
dynamic.list file.

Strictly speaking, any new functions added to malloc should be added
to dynamic.list so they're kept interposable. Since we're not planning
to call any of these from within libc, it doesn't make any difference,
but I'd still add them there for completeness and future-proofing.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Rich Felker]

On Thu, May 25, 2023 at 11:16:53AM +0200, Jₑₙₛ Gustedt wrote:
> Rich,
> 
> on Wed, 24 May 2023 17:28:35 -0400 you (Rich Felker <dalias@libc.org>)
> wrote:
> 
> > There's a more efficient implementation of this function which does
> > not depend on __builtin_ctzll (which we don't): p^(p-1)&p
> 
> yes, nice
> 
> If you have other such nice formulas for some of the interfaces in
> <stdbit.h>, please let me know. They are hard to find in search
> engines.
> 
> For `__builtin_ctzll`, hm, I counted also to use these for the
> <stdbit.h> interfaces. I think the intent of those is really to
> provide instruction level support of these bit functionalities that
> avoids going through function calls.
> 
> I see that we use other quite specific builtins, such as
> `__builtin_fma`. Is there a particular reason not to have the bit
> level ones?

That was probably an oversight. The intent of those is to expand to an
fma instruction, but AIUI there's no reason the compiler isn't allowed
to expand it to a call to the fma() function (like the other
__builtin_* versions of standard functions). That's not really a
problem here, but it *could be* in other cases where the definition
may end up being circular.

Really these should be cleaned up to have src/include/*.h recover some
of the builtins that -ffreestanding had to suppress (to prevent
circularity) where they're useful, conditional on probing for compiler
support, rather than using them directly in the code. Then log, pow,
and log2 could just call fma(). More importantly, a lot of
memcpy/memset use could be inlined where it can't now.

> So you want me to use the ctz and clz interfaces from the internal
> atomics for the implementation of <stdbit.h>? Are they not overkill
> for this simple purpose? (I mean they are meant to be atomic, arent't
> they?)

No, I think you're mixing up code which is part of musl and code which
is (included as) part of the application. atomic.h is a musl
implementation detail and is not even present for application code
included from stdbit.h to use.

> > I'm not clear that there's a really good motivation for having it
> > implemented in the header. It kinda falls under the "maybe do it
> > because it's easy" case, but once you switch to the non-GNUC-specific
> > version, it needs a static inline function to avoid multiple
> > evaluation,
> 
> I guess using `({ ... })` would also not be acceptable?

It's presently outside the limited set of GNU C we use, and I'd prefer
to keep it that way.

> > and then it gets to the point of "this is really too much
> > code to have in a header" (which is more an issue of avoiding
> > "creative" content in headers than anything else).
> 
> You probably won't like what I have now for the bit operations, then
> :-(

See NRK's follow-up. If pure header-only implementations of these
interfaces met the requirements of the standard, I could see a good
argument for having implementations there. But if they require
external functions, I'm not clear on why it makes sense to implement
inline versions in the headers rather than just letting the compiler
do its own transformations to inline if/when it wants. This was a path
glibc went down a long time ago with "bits/string2.h", putting gobs of
attempted-optimized code in public headers that was suppressing gcc's
builtin, much better optimizations for the same functions via its
__builtin_*. I don't think we should repeat that.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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


on Thu, 25 May 2023 09:07:23 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> > So you want me to use the ctz and clz interfaces from the internal
> > atomics for the implementation of <stdbit.h>? Are they not overkill
> > for this simple purpose? (I mean they are meant to be atomic,
> > arent't they?)  
> 
> No, I think you're mixing up code which is part of musl and code which
> is (included as) part of the application. atomic.h is a musl
> implementation detail and is not even present for application code
> included from stdbit.h to use.

I am not clear to which question you are answering "no". Fact is that
these functions are used for `ffs` and friends, so they are the
natural candidates to base the implementation upon. (`ffs` cannot be
used directly because they have intefaces with signed integers.)

I'd very much like to avoid to reinvent the wheel, here, and in the
internal code that I have looked at I have not detected much which
would be specific for atomics. But maybe I am overlooking something,
thus the question.

> See NRK's follow-up. If pure header-only implementations of these
> interfaces met the requirements of the standard, I could see a good
> argument for having implementations there. But if they require
> external functions, I'm not clear on why it makes sense to implement
> inline versions in the headers rather than just letting the compiler
> do its own transformations to inline if/when it wants. This was a path
> glibc went down a long time ago with "bits/string2.h", putting gobs of
> attempted-optimized code in public headers that was suppressing gcc's
> builtin, much better optimizations for the same functions via its
> __builtin_*. I don't think we should repeat that.

Yes, thanks, I understand that strategy much better now.

Thanks
Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Rich Felker]

On Thu, May 25, 2023 at 04:05:01PM +0200, Jₑₙₛ Gustedt wrote:
> 
> on Thu, 25 May 2023 09:07:23 -0400 you (Rich Felker <dalias@libc.org>)
> wrote:
> 
> > > So you want me to use the ctz and clz interfaces from the internal
> > > atomics for the implementation of <stdbit.h>? Are they not overkill
> > > for this simple purpose? (I mean they are meant to be atomic,
> > > arent't they?)  
> > 
> > No, I think you're mixing up code which is part of musl and code which
> > is (included as) part of the application. atomic.h is a musl
> > implementation detail and is not even present for application code
> > included from stdbit.h to use.
> 
> I am not clear to which question you are answering "no". Fact is that
> these functions are used for `ffs` and friends, so they are the
> natural candidates to base the implementation upon. (`ffs` cannot be
> used directly because they have intefaces with signed integers.)

OK, maybe I misunderstood. They can and should be used in musl sources
for implementing these interfaces as external functions, just not for
macro definitions in the headers. I thought we were talking about the
latter.

It looks like the primitives we have cover everything needed for
stdbit.h functions except popcnt. Not sure what the best way to add
that is. Perhaps with a new a_popcnt that archs can override. This
would also allow configure to probe for a builtin and select use of
that if desired. It looks like that generates a call to libgcc on
archs with no native version.

> I'd very much like to avoid to reinvent the wheel, here, and in the
> internal code that I have looked at I have not detected much which
> would be specific for atomics. But maybe I am overlooking something,
> thus the question.

Having them in "atomics" is a historical misnomer, but it's vacuous
since they operate on values not objects. The effort to move them to a
separate file and setup per-arch machinery for defining them there is
nontrivial and the value seems near-zero, so I haven't pursued it.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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


on Thu, 25 May 2023 10:34:15 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> It looks like the primitives we have cover everything needed for
> stdbit.h functions except popcnt.

yes

> Not sure what the best way to add that is. Perhaps with a new
> a_popcnt that archs can override. This would also allow configure to
> probe for a builtin and select use of that if desired. It looks like
> that generates a call to libgcc on archs with no native version.

ok, there seems to be a relatively easy approach on the bithacks site
for that.

In any case, this can wait a bit, since there are still some questions
about this header that will be decided by WG14 in the June
session. Namely there are some redundancies (and even repetition) in
the interfaces, so we will see which of them survives.

Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Alexander Monakov]

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


On Thu, 25 May 2023, Jₑₙₛ Gustedt wrote:

> Rich,
> 
> on Wed, 24 May 2023 17:28:35 -0400 you (Rich Felker <dalias@libc.org>)
> wrote:
> 
> > There's a more efficient implementation of this function which does
> > not depend on __builtin_ctzll (which we don't): p^(p-1)&p
> 
> yes, nice
> 
> If you have other such nice formulas for some of the interfaces in
> <stdbit.h>, please let me know. They are hard to find in search
> engines.

It seems this was unanswered. Hacker's Delight by Henry Warren offers
a lot of material on such topics. For this particular question it also
gives the efficient implementation: 'p & -p'.

I looked over the recently posted stdbit.h patch and I don't have anything
to suggest in terms of formulas. The things that would worry me are of a
different nature anyway.

Alexander

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Rich Felker]

On Thu, Jun 01, 2023 at 04:35:04PM +0300, Alexander Monakov wrote:
> 
> On Thu, 25 May 2023, Jₑₙₛ Gustedt wrote:
> 
> > Rich,
> > 
> > on Wed, 24 May 2023 17:28:35 -0400 you (Rich Felker <dalias@libc.org>)
> > wrote:
> > 
> > > There's a more efficient implementation of this function which does
> > > not depend on __builtin_ctzll (which we don't): p^(p-1)&p
> > 
> > yes, nice
> > 
> > If you have other such nice formulas for some of the interfaces in
> > <stdbit.h>, please let me know. They are hard to find in search
> > engines.
> 
> It seems this was unanswered. Hacker's Delight by Henry Warren offers
> a lot of material on such topics. For this particular question it also
> gives the efficient implementation: 'p & -p'.

Wow, I don't know why I didn't realize this being that p&-p is a
common pattern I use... Somehow I didn't see that it was the same
operation.

Rich

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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

Alexander,

on Thu, 1 Jun 2023 16:35:04 +0300 (MSK) you (Alexander Monakov
<amonakov@ispras.ru>) wrote:

> On Thu, 25 May 2023, Jₑₙₛ Gustedt wrote:
> 
> > Rich,
> > 
> > on Wed, 24 May 2023 17:28:35 -0400 you (Rich Felker
> > <dalias@libc.org>) wrote:
> >   
> > > There's a more efficient implementation of this function which
> > > does not depend on __builtin_ctzll (which we don't): p^(p-1)&p  
> > 
> > yes, nice
> > 
> > If you have other such nice formulas for some of the interfaces in
> > <stdbit.h>, please let me know. They are hard to find in search
> > engines.  
> 
> It seems this was unanswered. Hacker's Delight by Henry Warren offers
> a lot of material on such topics. For this particular question it also
> gives the efficient implementation: 'p & -p'.

right, even better

> I looked over the recently posted stdbit.h patch and I don't have
> anything to suggest in terms of formulas. The things that would worry
> me are of a different nature anyway.

Could you share those that concern this particular new header
<stdbit.h> ? (Perhaps in the thread with the patches?)

Thanks
Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Jₑₙₛ Gustedt]

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

Rich,

on Thu, 1 Jun 2023 15:08:04 -0400 you (Rich Felker <dalias@libc.org>)
wrote:

> Wow, I don't know why I didn't realize this being that p&-p is a
> common pattern I use... Somehow I didn't see that it was the same
> operation.

Don't worry this seems to be quite common. As currently proposed this
header tries to interface all the different extensions that are out
there. By doing so, it seems that none of WG14 had noticed that there
is a duplicate pair of functions that have different names but do
exactly the same thing.

Jₑₙₛ

-- 
:: ICube :::::::::::::::::::::::::::::: deputy director ::
:: Université de Strasbourg :::::::::::::::::::::: ICPS ::
:: INRIA Nancy Grand Est :::::::::::::::::::::::: Camus ::
:: :::::::::::::::::::::::::::::::::::: ☎ +33 368854536 ::
:: https://icube-icps.unistra.fr/index.php/Jens_Gustedt ::

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

Re: [musl] [C23 new stdlib 2/4] C23: add the memalignment function

[Alexander Monakov]

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


On Fri, 2 Jun 2023, Jₑₙₛ Gustedt wrote:

> > I looked over the recently posted stdbit.h patch and I don't have
> > anything to suggest in terms of formulas. The things that would worry
> > me are of a different nature anyway.
> 
> Could you share those that concern this particular new header
> <stdbit.h> ? (Perhaps in the thread with the patches?)

They are unrelated to the implementation, so totally off-topic.

Alexander