rust: alloc: satisfy `aligned_alloc` requirements

The implementation added in commit dd09538fb409 ("rust: alloc: implement Cmalloc in module allocator_test") did not honor the documented requirements of aligned_alloc. These requirements may not be enforced on all systems, but they are on macOS. Ensure that alignment is at least sizeof(void *) and round size up to the nearest multiple of that value.

---
Changes in v2:
- Shorten some variable names. (Danilo Krummrich)
- Replace shadowing alignment variable with a second call to
Layout::align. (Danilo Krummrich)
- Link to v1: https://lore.kernel.org/r/[email protected]

---
 rust/kernel/alloc/allocator_test.rs | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

index e3240d16040b..69f79e246891 100644
@@ -62,9 +62,21 @@ unsafe fn realloc(
             ));
         }
 
+        // According to `man aligned_alloc`:
+        //
+        // aligned_alloc() returns a NULL pointer and sets errno to EINVAL if size is not an
+        // integral multiple of alignment, or if alignment is not a power of 2 at least as large as
+        // sizeof(void *).
+        let min_align = core::mem::size_of::<*const crate::ffi::c_void>();
+        let (align, size) = if layout.align() < min_align {
+            (min_align, layout.size().div_ceil(min_align) * min_align)
+        } else {
+            (layout.align(), layout.size())
+        };
+
         // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or
         // exceeds the given size and alignment requirements.
-        let dst = unsafe { libc_aligned_alloc(layout.align(), layout.size()) } as *mut u8;
+        let dst = unsafe { libc_aligned_alloc(align, size) } as *mut u8;
         let dst = NonNull::new(dst).ok_or(AllocError)?;
 
         if flags.contains(__GFP_ZERO) {

---
base-commit: 89a010129b2a60185d34d7377ef8aec7fbb92e76
change-id: 20250201-aligned-alloc-b52cb2353c82

Best regards,

Tamir Duberstein <[email protected]>

Which requirements? aligned_alloc comes from ISO C, and POSIX says it is aligned with it; i.e. the change to make it work in macOS seems fine, but please see below.

Hmm... I don't have this base commit (but the patch applied fine).

Thanks!

Cheers,
Miguel

I previously checked man posix_memalign(3) and it says:

ERRORS
EINVAL The alignment argument was not a power of two, or was not a
multiple of sizeof(void *).

Right. The best description seems to be on
https://en.cppreference.com/w/c/memory/aligned_alloc. ISO C says:

Meanwhile POSIX says of posix_memalign:

The note on cppreference addresses this:

I could rework this patch to use posix_memalign which seems to be more completely defined, or I can try to capture all this detail in a code comment and the commit message. What do you folks prefer?

Yes, at least some POSIX-based implementation inherit some requirements, but the commit talks about the "documented requirements" of alligned_alloc, which didn't seem right to me (in fact, some implementations seem to be extremely lax (e.g. glibc)).

I suggested going with that "macOS" etc. line because that is what we are doing and so that we avoid having to put a lot of complexity in that comment.

In other words, we are changing it so that it works in macOS, right? And those requirements seem the stricter ones vs. say glibc ones. So going with the "why we changed this" may be an easier way to explain why we are actually changing this, unless we are sure we know those are the requirements for everyone (which is what the current comment in the code looks like).

But if using another function makes it clearer, that is great too.

In any case, to be clear, I didn't want to delay the change -- it is just that the commit message and the comment didn't seem correct.

Thanks!

Cheers,
Miguel

You're absolutely correct, of course. I've changed this to use posix_memalign so that the behavior is identical for everyone. I'll send v3 shortly.

Thank you!
Tamir

Yeah, but that may not apply to alligned_alloc as far as I can see.

Cheers,
Miguel

What makes you think so?

AFAICS, the man page applies for posix_memalign, aligned_alloc, memalign, valloc and pvalloc.

In case behavior differs between the functions, this is stated explicitly, e.g. in the "RETURN VALUE" section.

The "ERRORS" setion does not differentiate, hence it should apply to all the functions above, including aligned_alloc.

Do I miss anything?

The writing is definitely obtuse.

It seems that the errors section applies to posix_memalign only. The description section also contains:

So aligned_alloc has the same alignment requirement as memalign, which is only that it's a power of two.

The explanation of the requirements (in the Linux man page) mention different requirements for each function.

Moreover, in practice, glibc seemed to allow almost any alignment up to 2023, and since then they have this:

+/* Similar to memalign, but starting with ISO C17 the standard
+ requires an error for alignments that are not supported by the
+ implementation. Valid alignments for the current implementation
+ are non-negative powers of two. */
+ if (!powerof2 (alignment) || alignment == 0)
+ {
+ __set_errno (EINVAL);
+ return 0;
+ }

Including a test that does not fail for a degenerate alignment (1). Thus I don't think the "multiple of sizeof" part applies today or in the past for that implementation (again, in practice).

But I don't know how those sections are formally supposed to work or what requirements (and/or behavior) the man pages are supposed to be documenting -- Cc'ing Alejandro. It seems clarifying the page would help.

Cheers,
Miguel

Indeed, it seems a bit ambiguous.

Agree, in practice no concern from my side either.

+1

[CC += DJ, Eric, Will, Paul, linux-man@]

Hi Miguel,

Here's my understanding after reading these pages in the Linux man-pages project, the POSIX description, and doing some experiments:

- memalign()

It doesn't validate the input. It over-aligns the pointer silently if necessary. The text doesn't seem to match reality; I think the following diff would fix the description to match reality:

diff --git i/man/man3/posix_memalign.3 w/man/man3/posix_memalign.3 index b760cf271..a4da60eb3 100644
--- i/man/man3/posix_memalign.3
+++ w/man/man3/posix_memalign.3
@@ -77,14 +77,13 @@ .SH DESCRIPTION
The obsolete function
.BR memalign ()
allocates
.I size
bytes and returns a pointer to the allocated memory.
The memory address will be a multiple of
-.IR alignment ,
-which must be a power of two.
+.IR alignment .
.\" The behavior of memalign() for size==0 is as for posix_memalign() .\" but no standards govern this.
.P
.BR aligned_alloc ()
is the same as
.BR memalign (),

That text might have been true in some ancient C library. I don't know. It just doesn't seem true now.

- aligned_alloc()

It seems to be like memalign(), with *some* input validation. It makes sure that the input is a power of two, or it fails. However, it doesn't check that the input is multiple of _Alignof(void*). That requirement is implementation-defined; neither POSIX nor ISO C impose any specific requirements, so the requirements that the input is a power of two are imposed by glibc. The documentation matches the experimental behavior.

- posix_memalign()

This function is similar to aligned_alloc(), with an unfortunate prototype (it returns the new memory via an output parameter, which makes it a bit unsafer in C --you can't apply the [[gnu::malloc()]] attribute, for example; and static analyzers might be confused if the pointer is uninitialized--), but with stricter requirements. It requires that the input is power of two, and multiple of _Alignof(void*), and those requirements are mandated by POSIX.

Below is a text program that shows all of this.

I wonder why glibc silently overaligns aligned_alloc() without reporting an error for an alignment of 2, while it reports an error for an alignment of 3. It doesn't make much sense at first glance. No standard seems to require that, so it looks like an arbitrary choice.

alx@devuan:~/tmp/gcc$ cat m.c 
#define _GNU_SOURCE
#include <errno.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

int
main(void)

{
	int   i;
	void  *p;

	puts("prime number");

	errno = 0;
	i = posix_memalign(&p, 3, 3);
	printf("posix_memalign(, 3, 3): %s; %#m\n", strerrorname_np(i));

	errno = 0;
	p = aligned_alloc(3, 3);
	printf("aligned_alloc(3, 3): %p; %#m\n", p);

	errno = 0;
	p = valloc(3);
	printf("valloc(3): %p; %#m\n", p);

	errno = 0;
	p = memalign(3, 3);
	printf("memalign(3, 3): %p; %#m\n", p);

	errno = 0;
	p = pvalloc(3);
	printf("pvalloc(3): %p; %#m\n", p);

	puts("");
	puts("Power of two, but not alignof(void*)");

	errno = 0;
	i = posix_memalign(&p, 2, 2);
	printf("posix_memalign(, 2, 2): %s; %#m\n", strerrorname_np(i));

	errno = 0;
	p = aligned_alloc(2, 2);
	printf("aligned_alloc(2, 2): %p; %#m\n", p);

	errno = 0;
	p = valloc(2);
	printf("valloc(2): %p; %#m\n", p);

	errno = 0;
	p = memalign(2, 2);
	printf("memalign(2, 2): %p; %#m\n", p);

	errno = 0;
	p = pvalloc(2);
	printf("pvalloc(2): %p; %#m\n", p);

	puts("");
	puts("non-power of two, alignof(void*)");

	errno = 0;
	i = posix_memalign(&p, 24, 24);
	printf("posix_memalign(, 24, 24): %s; %#m\n", strerrorname_np(i));

	errno = 0;
	p = aligned_alloc(24, 24);
	printf("aligned_alloc(24, 24): %p; %#m\n", p);

	errno = 0;
	p = valloc(24);
	printf("valloc(24): %p; %#m\n", p);

	errno = 0;
	p = memalign(24, 24);
	printf("memalign(24, 24): %p; %#m\n", p);

	errno = 0;
	p = pvalloc(24);
	printf("pvalloc(24): %p; %#m\n", p);

	puts("");
	puts("Power of two, alignof(void*)");

	errno = 0;
	i = posix_memalign(&p, 8, 8);
	printf("posix_memalign(, 8, 8): %s; %#m\n", strerrorname_np(i));

	errno = 0;
	p = aligned_alloc(8, 8);
	printf("aligned_alloc(8, 8): %p; %#m\n", p);

	errno = 0;
	p = valloc(8);
	printf("valloc(8): %p; %#m\n", p);

	errno = 0;
	p = memalign(8, 8);
	printf("memalign(8, 8): %p; %#m\n", p);

	errno = 0;
	p = pvalloc(8);
	printf("pvalloc(8): %p; %#m\n", p);

	puts("");
	puts("Zero");

	errno = 0;
	i = posix_memalign(&p, 0, 0);
	printf("posix_memalign(, 0, 0): %s; %#m\n", strerrorname_np(i));

	errno = 0;
	p = aligned_alloc(0, 0);
	printf("aligned_alloc(0, 0): %p; %#m\n", p);

	errno = 0;
	p = valloc(0);
	printf("valloc(0): %p; %#m\n", p);

	errno = 0;
	p = memalign(0, 0);
	printf("memalign(0, 0): %p; %#m\n", p);

	errno = 0;
	p = pvalloc(0);
	printf("pvalloc(0): %p; %#m\n", p);
}
alx@devuan:~/tmp/gcc$ cc m.c 
alx@devuan:~/tmp/gcc$ ./a.out 
prime number
posix_memalign(, 3, 3): EINVAL; 0
aligned_alloc(3, 3): (nil); EINVAL
valloc(3): 0x55c7f4d9a000; 0
memalign(3, 3): 0x55c7f4d996b0; 0
pvalloc(3): 0x55c7f4d9b000; 0

Power of two, but not alignof(void*)
posix_memalign(, 2, 2): EINVAL; 0
aligned_alloc(2, 2): 0x55c7f4d996d0; 0
valloc(2): 0x55c7f4d9d000; 0
memalign(2, 2): 0x55c7f4d996f0; 0
pvalloc(2): 0x55c7f4d9e000; 0

non-power of two, alignof(void*)
posix_memalign(, 24, 24): EINVAL; 0
aligned_alloc(24, 24): (nil); EINVAL
valloc(24): 0x55c7f4da0000; 0
memalign(24, 24): 0x55c7f4d99740; 0
pvalloc(24): 0x55c7f4da1000; 0

Power of two, alignof(void*)
posix_memalign(, 8, 8): 0; 0
aligned_alloc(8, 8): 0x55c7f4d99760; 0
valloc(8): 0x55c7f4da3000; 0
memalign(8, 8): 0x55c7f4d99780; 0
pvalloc(8): 0x55c7f4da4000; 0

Zero
posix_memalign(, 0, 0): EINVAL; 0
aligned_alloc(0, 0): (nil); EINVAL
valloc(0): 0x55c7f4da6000; 0
memalign(0, 0): 0x55c7f4d997a0; 0
pvalloc(0): 0x55c7f4da7000; 0

Have a lovely night!
Alex

<https://www.alejandro-colomar.es/>

Why doesn't it make sense?

If the underlying memory management system supports only some power-of-two alignments including one alignment greater than 2, it is easy to support alignment of 2 by overaligning, but it is not possible to support an alignment of 3.

Hi Paul,

Hmmm, I thought the memory management system could find some overalignment that would be multiple of 3 and that could work (maybe 3 * page size, as a big hammer). But maybe some implementation details just don't allow that, so I guess it's fair to reject it. Sounds reasonable.

Do you happen to know why the memalign(3) description says that the alignment must be a power of two when it doesn't do any validation and just rounds up as necessary? I'll send a patch for the manual page, but it would be good to know if something has changed about it at some point. Maybe in the past it did have different requirements?

Have a lovely night!
Alex

	alx@devuan:~/tmp/gcc$ cat overalign.c 
	#define _GNU_SOURCE
	#include <errno.h>
	#include <malloc.h>
	#include <stdlib.h>
	#include <string.h>

	int
	main(void)
	{
		int   i;
		void  *p;

		errno = 0;
		p = aligned_alloc(3, 3);
		printf("aligned_alloc(3, 3): %p; %#m\n", p);

		puts("");
		puts("non-power of two, alignof(void*)");

		errno = 0;
		p = aligned_alloc(24, 24);
		printf("aligned_alloc(24, 24): %p; %#m\n", p);

		puts("");
		puts("Power of two, alignof(void*)");

		errno = 0;
		p = aligned_alloc(8, 8);
		printf("aligned_alloc(8, 8): %p; %#m\n", p);
	}
	alx@devuan:~/tmp/gcc$ cc overalign.c 
	alx@devuan:~/tmp/gcc$ ./a.out 
	aligned_alloc(3, 3): (nil); EINVAL

	non-power of two, alignof(void*)
	aligned_alloc(24, 24): (nil); EINVAL

	Power of two, alignof(void*)
	aligned_alloc(8, 8): 0x55ba005056b0; 0

<https://www.alejandro-colomar.es/>

Because 2 is a power of two, but 3 isn't. No power of two is a multiple of 3.

GNU malloc only supports alignments that are powers of two. The resulting addresses might *happen* to be multiples of other numbers, but you cannot request that.

As for why, ask Posix:

"If the value of alignment is not a valid alignment supported by the
implementation, a null pointer shall be returned." [EINVAL]
The value of alignment is not a valid alignment supported by the implementation."

Thanks Alejandro.

I am not sure I agree -- I am confused about three points:

- I am not sure the documentation is matching the experimental
behavior. For instance, the Linux man pages say:

"except for the added restriction that size should be a
multiple of alignment"

But a call like aligned_alloc(8, 9) succeeds. What does "added
restriction" mean in this context? i.e. is it supposed to fail?

- I am not sure if ISO C intends to require the power of two or not.
One of the C23 drafts says aligned_alloc() is supposed to fail if

"the value of alignment is not a valid alignment supported by
the implementation the function"

And then, elsewhere, that:

"Valid alignments include only fundamental alignments, plus an
additional implementation-defined set of values, which can be empty. Every valid alignment value shall be a nonnegative integral power of two."

So if those are intended to be connected, then it sounds like a
non-power-of-two is invalid and thus the function should fail.

- What Danilo mentioned about the sections, e.g. is the "ERRORS"
section in the Linux man pages supposed to apply to all the functions documented in the same page?

Would it help to somehow indicate which errors apply for each function?

Thanks a lot!

Cheers,
Miguel

Hi Miguel,

Your manual page is too old. :)

commit 7fd1e0f2be216a5e7f7aef0d03304bdf81bca9e0
Author: DJ Delorie <[email protected]>
Date: Mon May 8 20:43:35 2023 -0400

posix_memalign.3: Update aligned_alloc(3) to match C17

diff --git a/man3/posix_memalign.3 b/man3/posix_memalign.3 index 9bc6eb9a4..88e4a8b63 100644
--- a/man3/posix_memalign.3
+++ b/man3/posix_memalign.3
@@ -91,9 +91,8 @@ .SH DESCRIPTION
is the same as
.BR memalign (),
except for the added restriction that
-.I size
-should be a multiple of
-.IR alignment .
+.I alignment
+must be a power of two.
.PP
The obsolete function
.BR valloc ()

On retrospective, we should have added some more details to that commit message. DJ, has the requirement of the size been lifted? Was it never present?

If the implementation in glibc has changed over time, we should probably add a HISTORY section documenting historic behavior.

Hmmm, you're probably true. I hadn't read that part.

It probably needs some rewrite to make it more generic for all functions.

Have a lovely night!
Alex

<https://www.alejandro-colomar.es/>

Thanks -- good to know it is fixed! Confirming in the VM where I found the 2023 glibc change, it does have the man pages is updated there too, so that is great.

At the very least, glibc made it stricter in d1417176a35d ("aligned_alloc: conform to C17") -- that is the 2023 change I referred to the other day. Before that, you could pretty much pass any alignment/size pair and it would succeed (small values).

Cheers,
Miguel

The current code checks alignment but not size.

It looks like that was always the case.

And no, I don't remember where I got the size requirement from ;-) (but at least it says "should" instead of "must")