Benno Lossin
2025-Jun-03 23:02 UTC
[PATCH v4 04/20] rust: add new `num` module with useful integer operations
On Mon Jun 2, 2025 at 3:09 PM CEST, Alexandre Courbot wrote:> On Thu May 29, 2025 at 4:27 PM JST, Benno Lossin wrote: >> On Thu May 29, 2025 at 3:18 AM CEST, Alexandre Courbot wrote: >>> On Thu May 29, 2025 at 5:17 AM JST, Benno Lossin wrote: >>>> On Wed May 21, 2025 at 8:44 AM CEST, Alexandre Courbot wrote: >>>>> + /// Align `self` up to `alignment`. >>>>> + /// >>>>> + /// `alignment` must be a power of 2 for accurate results. >>>>> + /// >>>>> + /// Wraps around to `0` if the requested alignment pushes the result above the type's limits. >>>>> + /// >>>>> + /// # Examples >>>>> + /// >>>>> + /// ``` >>>>> + /// use kernel::num::NumExt; >>>>> + /// >>>>> + /// assert_eq!(0x4fffu32.align_up(0x1000), 0x5000); >>>>> + /// assert_eq!(0x4000u32.align_up(0x1000), 0x4000); >>>>> + /// assert_eq!(0x0u32.align_up(0x1000), 0x0); >>>>> + /// assert_eq!(0xffffu16.align_up(0x100), 0x0); >>>>> + /// assert_eq!(0x4fffu32.align_up(0x0), 0x0); >>>>> + /// ``` >>>>> + fn align_up(self, alignment: Self) -> Self; >>>> >>>> Isn't this `next_multiple_of` [1] (it also allows non power of 2 >>>> inputs). >>>> >>>> [1]: https://doc.rust-lang.org/std/primitive.u32.html#method.next_multiple_of >>> >>> It is, however the fact that `next_multiple_of` works with non powers of >>> two also means it needs to perform a modulo operation. That operation >>> might well be optimized away by the compiler, but ACAICT we have no way >>> of proving it will always be the case, hence the always-optimal >>> implementation here. >> >> When you use a power of 2 constant, then I'm very sure that it will get >> optimized [1]. Even with non-powers of 2, you don't get a division [2]. >> If you find some code that is not optimized, then sure add a custom >> function. >> >> [1]: https://godbolt.org/z/57M9e36T3 >> [2]: https://godbolt.org/z/9P4P8zExh > > That's impressive and would definitely work well with a constant. But > when the value is not known at compile-time, the division does occur > unfortunately: https://godbolt.org/z/WK1bPMeEx > > So I think we will still need a kernel-optimized version of these > alignment functions.Hmm what exactly is the use-case for a variable align amount? Could you store it in const generics? If not, there are also these two variants that are more efficient: * option: https://godbolt.org/z/ecnb19zaM * unsafe: https://godbolt.org/z/EqTaGov71 So if the compiler can infer it from context it still optimizes it :) But yeah to be extra sure, you need your version. By the way, what happens if `align` is not a power of 2 in your version?>>> Also in the kernel we tend to use the `align` nomenclature and I think we >>> should preserve that for clarity. >> >> That's also fair, but we lose the constness of `next_multiple_of`, so >> you can't use `align_up` in a const function. That might confuse people >> and then they write their own const helper function... I'd prefer we use >> all functions that are available in the stdlib. > > We definitely want const variants of these, one way or the other (const > methods in traits are not available yet unfortunately). And yes, on > principle I am aligned (haha) with using stdlib functions when possible.Then I'd recommend getting in touch with upstream Rust :) And choose rusty names for our trait so we have an easy switch. --- Cheers, Benno
Alexandre Courbot
2025-Jun-04 00:05 UTC
[PATCH v4 04/20] rust: add new `num` module with useful integer operations
On Wed Jun 4, 2025 at 8:02 AM JST, Benno Lossin wrote:> On Mon Jun 2, 2025 at 3:09 PM CEST, Alexandre Courbot wrote: >> On Thu May 29, 2025 at 4:27 PM JST, Benno Lossin wrote: >>> On Thu May 29, 2025 at 3:18 AM CEST, Alexandre Courbot wrote: >>>> On Thu May 29, 2025 at 5:17 AM JST, Benno Lossin wrote: >>>>> On Wed May 21, 2025 at 8:44 AM CEST, Alexandre Courbot wrote: >>>>>> + /// Align `self` up to `alignment`. >>>>>> + /// >>>>>> + /// `alignment` must be a power of 2 for accurate results. >>>>>> + /// >>>>>> + /// Wraps around to `0` if the requested alignment pushes the result above the type's limits. >>>>>> + /// >>>>>> + /// # Examples >>>>>> + /// >>>>>> + /// ``` >>>>>> + /// use kernel::num::NumExt; >>>>>> + /// >>>>>> + /// assert_eq!(0x4fffu32.align_up(0x1000), 0x5000); >>>>>> + /// assert_eq!(0x4000u32.align_up(0x1000), 0x4000); >>>>>> + /// assert_eq!(0x0u32.align_up(0x1000), 0x0); >>>>>> + /// assert_eq!(0xffffu16.align_up(0x100), 0x0); >>>>>> + /// assert_eq!(0x4fffu32.align_up(0x0), 0x0); >>>>>> + /// ``` >>>>>> + fn align_up(self, alignment: Self) -> Self; >>>>> >>>>> Isn't this `next_multiple_of` [1] (it also allows non power of 2 >>>>> inputs). >>>>> >>>>> [1]: https://doc.rust-lang.org/std/primitive.u32.html#method.next_multiple_of >>>> >>>> It is, however the fact that `next_multiple_of` works with non powers of >>>> two also means it needs to perform a modulo operation. That operation >>>> might well be optimized away by the compiler, but ACAICT we have no way >>>> of proving it will always be the case, hence the always-optimal >>>> implementation here. >>> >>> When you use a power of 2 constant, then I'm very sure that it will get >>> optimized [1]. Even with non-powers of 2, you don't get a division [2]. >>> If you find some code that is not optimized, then sure add a custom >>> function. >>> >>> [1]: https://godbolt.org/z/57M9e36T3 >>> [2]: https://godbolt.org/z/9P4P8zExh >> >> That's impressive and would definitely work well with a constant. But >> when the value is not known at compile-time, the division does occur >> unfortunately: https://godbolt.org/z/WK1bPMeEx >> >> So I think we will still need a kernel-optimized version of these >> alignment functions. > > Hmm what exactly is the use-case for a variable align amount? Could you > store it in const generics?Say you have an IOMMU with support for different pages sizes, the size of a particular page can be decided at runtime.> > If not, there are also these two variants that are more efficient: > > * option: https://godbolt.org/z/ecnb19zaM > * unsafe: https://godbolt.org/z/EqTaGov71 > > So if the compiler can infer it from context it still optimizes it :)I think the `Option` (and subsequent `unwrap`) is something we want to avoid on such a common operation.> > But yeah to be extra sure, you need your version. By the way, what > happens if `align` is not a power of 2 in your version?It will just return `(self + (self - 1)) & (alignment - 1)`, which will likely be a value you don't want. So yes, for this particular operation we would prefer to only use powers of 2 as inputs - if we can ensure that then it solves most of our problems (can use `next_multiple_of`, no `Option`, etc). Maybe we can introduce a new integer type that, similarly to `NonZero`, guarantees that the value it stores is a power of 2? Users with const values (90+% of uses) won't see any difference, and if working with a runtime-generated value we will want to validate it anyway... (I can already hear you saying "send that to upstream Rust!" ^_^;)