LWN: Comments on "Implementing alignment guarantees for kmalloc()"

Implementing alignment guarantees for kmalloc()

rweikusat2 — Wed, 23 Oct 2019 14:20:33 +0000

The expression was n & ~(-1 + n). That's a slightly steganographically obscured version of n & ~(n - 1). Assuming that n is some non-zero binary number, subtracting one from that causes the lowest set 1 bit to change to 0 and all 0 bits below it to 1. All other 1 bits of n are also 1 in n - 1. Hence n & ~(n - 1) leaves only the lowest bit of n set.

Implementing alignment guarantees for kmalloc()

wilevers — Tue, 22 Oct 2019 19:55:02 +0000

Try parsing this. Then again. Any questions?

Implementing alignment guarantees for kmalloc()

jreiser — Mon, 21 Oct 2019 16:48:26 +0000

The new alignment guarantees are only for power of two sizes... The result should be aligned to min(PAGE_SIZE, n & ~(-1+n)), which is the place value of the lowest-order '1' bit in the requested size (but limited to the sizeof one page). So if the request is for 40 bytes then the result should be 8-byte aligned. The rationale is: the alignment of a struct having that size.

Implementing alignment guarantees for kmalloc()

vbabka — Mon, 21 Oct 2019 07:56:41 +0000

> I think the question is more whether there are any callers that have a specific requirement for unaligned allocations, that is, cases where there are so many tiny allocations that the wasted space matters. And if they exist, whether they wouldn't be better served with large requests to kmalloc() feeding to their own internal allocator which portions them out into tiny slices.

The new alignment guarantees are only for power of two sizes, and that's when the common SLAB and SLUB configurations already don't waste any memory. For other sizes, kmalloc() will mostly round them up to the nearest power-of-two anyway (exceptions are 96 and 192 bytes, see your /proc/slabinfo), so the waste comes from that. Those who allocate significant number of "oddly sized" objects should create own cache for them by kmem_cache_create() with precise size and optional alignment, which will minimize the waste.

Implementing alignment guarantees for kmalloc()

Cyberax — Sun, 20 Oct 2019 23:36:07 +0000

> I think the question is more whether there are any callers that have a specific requirement for unaligned allocations, that is, cases where there are so many tiny allocations that the wasted space matters.
Typically such unspoken ABIs are extended explicitly, by adding new flags.

So by default kmalloc() should return an aligned block, but there should be a flag explicitly requesting unaligned block. This way there won't be a need to have multiple allocators in each subsystem needing this.

Implementing alignment guarantees for kmalloc()

epa — Sun, 20 Oct 2019 19:28:07 +0000

Because the kernel is full of callers whose intent is to get aligned access, but don't explicitly specify it. Why do I say their intent is to get aligned access? Simply because of the fact that access always has been aligned up to now, in all but a few oddball configurations. If it almost always behaves that way in practice, any support in callers for unaligned access won't get exercised and will inevitably rot away. By the same argument you can say that malloc() (in user space / libc) is effectively an API that never returns null on failure, since it never does so in practice and nobody writes application code that handles it correctly; even with the best of intentions such code wouldn't get exercised enough for it to have a chance of working correctly.

I think the question is more whether there are any callers that have a specific requirement for unaligned allocations, that is, cases where there are so many tiny allocations that the wasted space matters. And if they exist, whether they wouldn't be better served with large requests to kmalloc() feeding to their own internal allocator which portions them out into tiny slices.

(This from the perspective of a non-kernel-developer, but the same issue arises in any API, having only one real implementation, where a particular behaviour is theoretically possible but doesn't arise in practice. In my view the answer is almost always to tighten up the specification, codifying the implicit guarantees that have held up to now.)

Implementing alignment guarantees for kmalloc()

wilevers — Sun, 20 Oct 2019 18:39:40 +0000

I'm confused. Why can't we have a separate API for callers that have a specific alignment requirement? That would allow any allocator to optimally supply what is expected instead of having to guess the caller's intent.