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

Fri Jun 13 05:31:02 UTC 2025

On Thu Jun 12, 2025 at 11:49 PM JST, Benno Lossin wrote:
> 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

Thanks for checking it! My x86 assembly literacy dates from a time when
32-bit registers were considered fancy, but it indeed seems to be
slightly more compact and faster. I guess alongside the lack of unsafe
block this makes me favor this version for now.