Message-Id: <20250430.225131.834272625051818223.fujita.tomonori@gmail.com>
Date: Wed, 30 Apr 2025 22:51:31 +0900 (JST)
From: FUJITA Tomonori <fujita.tomonori@...il.com>
To: miguel.ojeda.sandonis@...il.com
Cc: fujita.tomonori@...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, boqun.feng@...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 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?

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