[PATCH v4 04/20] rust: add new `num` module with useful integer operations

[Alexandre Courbot]

On Thu Jun 12, 2025 at 10:17 PM JST, Alexandre Courbot wrote:
> On Wed Jun 4, 2025 at 4:18 PM JST, Benno Lossin wrote:
>> On Wed Jun 4, 2025 at 2:05 AM CEST, Alexandre Courbot wrote:
>>> 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.
>>
>> Makes sense.
>>
>>>> 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 wouldn't it be better to make users validate that they gave a
>> power-of-2 alignment?
>>
>>> 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 like this idea. But it will mean that we have to have a custom
>> function that is either standalone and const or in an extension trait :(
>> But for this one we can use the name `align_up` :)
>>
>> Here is a cool idea for the implementation: https://godbolt.org/z/x6navM5WK
>
> Yeah that's close to what I had in mind.

... with one difference though: I would like to avoid the use of
`unsafe` for something so basic, so the implementation is close to the C
one (using masks and logical operations). I think it's a great
demonstration of the compiler's abilities that we can generate an
always-optimized version of `next_multiple_of`, but for our use-case it
feels like jumping through hoops just to show that we can jump through
these hoops. I'll reconsider if there is pushback on v5 though. :)