Message-ID: <aBI4mEgKx23qh1Zp@Mac.home>
Date: Wed, 30 Apr 2025 07:50:00 -0700
From: Boqun Feng <boqun.feng@...il.com>
To: FUJITA Tomonori <fujita.tomonori@...il.com>
Cc: miguel.ojeda.sandonis@...il.com, a.hindborg@...nel.org,
	rust-for-linux@...r.kernel.org, gary@...yguo.net,
	aliceryhl@...gle.com, me@...enk.dev, daniel.almeida@...labora.com,
	linux-kernel@...r.kernel.org, netdev@...r.kernel.org,
	andrew@...n.ch, hkallweit1@...il.com, tmgross@...ch.edu,
	ojeda@...nel.org, alex.gaynor@...il.com, bjorn3_gh@...tonmail.com,
	benno.lossin@...ton.me, a.hindborg@...sung.com,
	anna-maria@...utronix.de, frederic@...nel.org, tglx@...utronix.de,
	arnd@...db.de, jstultz@...gle.com, sboyd@...nel.org,
	mingo@...hat.com, peterz@...radead.org, juri.lelli@...hat.com,
	vincent.guittot@...aro.org, dietmar.eggemann@....com,
	rostedt@...dmis.org, bsegall@...gle.com, mgorman@...e.de,
	vschneid@...hat.com, tgunders@...hat.com,
	david.laight.linux@...il.com, pbonzini@...hat.com,
	jfalempe@...hat.com, linux@...linux.org.uk,
	chrisi.schrefl@...il.com, linus.walleij@...aro.org
Subject: Re: [PATCH v15 5/6] rust: time: Add wrapper for fsleep() function

On Wed, Apr 30, 2025 at 10:51:31PM +0900, FUJITA Tomonori wrote:
> On Tue, 29 Apr 2025 16:35:09 +0200
> Miguel Ojeda <miguel.ojeda.sandonis@...il.com> wrote:
> 
> >> It appears that there is still no consensus on how to resolve it. CC
> >> the participants in the above thread.
> >>
> >> I think that we can drop this patch and better to focus on Instant and
> >> Delta types in this merge window.
> >>
> >> With the patch below, this issue could be resolved like the C side,
> >> but I'm not sure whether we can reach a consensus quickly.
> > 
> > I think using the C ones is fine for the moment, but up to what arm
> > and others think.
> 
> I don't think anyone would disagree with the rule Russell mentioned
> that expensive 64-bit by 64-bit division should be avoided unless
> absolutely necessary so we should go with function div_s64() instead
> of function div64_s64().
> 
> The DRM QR driver was already fixed by avoiding 64-bit division, so
> for now, the only place where we still need to solve this issue is the
> time abstraction. So, it seems like Arnd's suggestion to simply call
> ktime_to_ms() or ktime_to_us() is the right way to go.
> 
> > This one is also a constant, so something simpler may be better (and
> > it is also a power of 10 divisor, so the other suggestions on that
> > thread would apply too).
> 
> One downside of calling the C's functions is that the as_micros/millis
> methods can no longer be const fn (or is there a way to make that
> work?). We could implement the method Paolo suggested from Hacker's
> Delight, 2nd edition in Rust and keep using const fn, but I'm not sure
> if it's really worth it.
> 
> Any thoughts?
> 

For ARM, where the constant division optimization (into to mult/shift)
is not available, I'm OK with anything you and others come out with
(calling a C function, implementing our own optimization, etc.) For
other architectures where the compilers can do the right thing, I
suggest we use the compiler optimization and don't re-invent the wheel.
For example, in your div10() solution below, we can have a generic
version which just uses a normal division for x86, arm64, riscv, etc,
and an ARM specific version.

Btw, the const fn point is a good one, thanks for bringing that up.

Regards,
Boqun

> diff --git a/rust/kernel/time.rs b/rust/kernel/time.rs
> index a8089a98da9e..daf9e5925e47 100644
> --- a/rust/kernel/time.rs
> +++ b/rust/kernel/time.rs
> @@ -229,12 +229,116 @@ pub const fn as_nanos(self) -> i64 {
>      /// to the value in the [`Delta`].
>      #[inline]
>      pub const fn as_micros_ceil(self) -> i64 {
> -        self.as_nanos().saturating_add(NSEC_PER_USEC - 1) / NSEC_PER_USEC
> +        const NSEC_PER_USEC_EXP: u32 = 3;
> +
> +        div10::<NSEC_PER_USEC_EXP>(self.as_nanos().saturating_add(NSEC_PER_USEC - 1))
>      }
>  
>      /// Return the number of milliseconds in the [`Delta`].
>      #[inline]
>      pub const fn as_millis(self) -> i64 {
> -        self.as_nanos() / NSEC_PER_MSEC
> +        const NSEC_PER_MSEC_EXP: u32 = 6;
> +
> +        div10::<NSEC_PER_MSEC_EXP>(self.as_nanos())
> +    }
> +}
> +
> +/// Precomputed magic constants for division by powers of 10.
> +///
> +/// Each entry corresponds to dividing a number by `10^exp`, where `exp` ranges from 0 to 18.
> +/// These constants were computed using the algorithm from Hacker's Delight, 2nd edition.
> +struct MagicMul {
> +    mult: u64,
> +    shift: u32,
> +}
> +
> +const DIV10: [MagicMul; 19] = [
> +    MagicMul {
> +        mult: 0x1,
> +        shift: 0,
> +    },
> +    MagicMul {
> +        mult: 0x6666666666666667,
> +        shift: 66,
> +    },
> +    MagicMul {
> +        mult: 0xA3D70A3D70A3D70B,
> +        shift: 70,
> +    },
> +    MagicMul {
> +        mult: 0x20C49BA5E353F7CF,
> +        shift: 71,
> +    },
> +    MagicMul {
> +        mult: 0x346DC5D63886594B,
> +        shift: 75,
> +    },
> +    MagicMul {
> +        mult: 0x29F16B11C6D1E109,
> +        shift: 78,
> +    },
> +    MagicMul {
> +        mult: 0x431BDE82D7B634DB,
> +        shift: 82,
> +    },
> +    MagicMul {
> +        mult: 0xD6BF94D5E57A42BD,
> +        shift: 87,
> +    },
> +    MagicMul {
> +        mult: 0x55E63B88C230E77F,
> +        shift: 89,
> +    },
> +    MagicMul {
> +        mult: 0x112E0BE826D694B3,
> +        shift: 90,
> +    },
> +    MagicMul {
> +        mult: 0x036F9BFB3AF7B757,
> +        shift: 91,
> +    },
> +    MagicMul {
> +        mult: 0x00AFEBFF0BCB24AB,
> +        shift: 92,
> +    },
> +    MagicMul {
> +        mult: 0x232F33025BD42233,
> +        shift: 101,
> +    },
> +    MagicMul {
> +        mult: 0x384B84D092ED0385,
> +        shift: 105,
> +    },
> +    MagicMul {
> +        mult: 0x0B424DC35095CD81,
> +        shift: 106,
> +    },
> +    MagicMul {
> +        mult: 0x480EBE7B9D58566D,
> +        shift: 112,
> +    },
> +    MagicMul {
> +        mult: 0x39A5652FB1137857,
> +        shift: 115,
> +    },
> +    MagicMul {
> +        mult: 0x5C3BD5191B525A25,
> +        shift: 119,
> +    },
> +    MagicMul {
> +        mult: 0x12725DD1D243ABA1,
> +        shift: 120,
> +    },
> +];
> +
> +const fn div10<const EXP: u32>(val: i64) -> i64 {
> +    crate::build_assert!(EXP <= 18);
> +    let MagicMul { mult, shift } = DIV10[EXP as usize];
> +    let abs_val = val.wrapping_abs() as u64;
> +    let ret = ((abs_val as u128 * mult as u128) >> shift) as u64;
> +    if val < 0 {
> +        -(ret as i64)
> +    } else {
> +        ret as i64
>      }
>  }

Powered by blists - more mailing lists