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

[Benno Lossin]

On Thu Jun 12, 2025 at 3:27 PM CEST, Alexandre Courbot wrote:
> 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. Actually, we can also define
>> `align_up` and `align_down` within this new type, and these methods can
>> now be const since they are not implemented via a trait!

That sounds like a good idea.

> ... 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. :)

It's always a balance when to use `unsafe` vs when not to. For me using
`hint::unreachable` & `next_multiple_of` is much easier to read than 

    self.wrapping_add(alignment.wrapping_sub(1)).align_down(alignment)

given that `align_down` is

    self & !alignment.wrapping_sub(1)

But that is totally due to my lack of experience with raw bit
operations. I also looked at the resulting assembly again and it seems
like (not an assembly expert at all :) your safe version produces better
code: https://godbolt.org/z/qhMbG7Mqd

---
Cheers,
Benno