[PATCH] clk: sunxi-ng: Change NKMP algorithm for finding factors

[PATCH] clk: sunxi-ng: Change NKMP algorithm for finding factors

[Ondřej Jirman]

From: Ondrej Jirman <megi@xff.cz>

Current algorithm is very slow. It searches inefficiently in a brute
force manner through all possibilities all the time.

Eg. it does >1500 iterations on every rate change twice, because
ccu_nkmp_find_best() function is called multiple times per rate
change.

New algorithm determines correct NKMP factors typically in 1 to 3
iterations if precise factors can be determined for M = 1, P = 1,
which is a typical case. If CPU clock frequency can't be derived
precisely this drops to average 8 iterations needed to determine
the factors.

The results are identical to the original algorithm, except in cases
where the original algorithm does not try to satisfy SoC PLL clock
constraints, like N*K range 10..88 or P factor being limited to output
frequency < 240 MHz.

These restrictions are based on A64 SoC datasheet. Although they
are sometimes not documented for other Allwinner SoC variants or are
slightly different, this is still a significant improvement over
not respecting any physical restrictions at all, as the previous
algorithm did not. Hardcoding the values if fine, until someone
finds some reason for not to.

Motivation for this patch is that cpufreq schedutil scheduler thread
manages to load one core to 70% all the time just doing these calculations
while the core is running at just 24MHz during frequency changes.
This helps improve the performance significantly.

Signed-off-by: Ondrej Jirman <megi@xff.cz>
---
Sorry, I don't know how to avoid overlong lines here, other than
maybe not indenting 3 toplevel for blocks and keeping all of them
at the same level.

 drivers/clk/sunxi-ng/ccu_nkmp.c | 80 ++++++++++++++++++++++-----------
 1 file changed, 55 insertions(+), 25 deletions(-)

diff --git a/drivers/clk/sunxi-ng/ccu_nkmp.c b/drivers/clk/sunxi-ng/ccu_nkmp.c
index 25efb5b37607..c39b19891431 100644
--- a/drivers/clk/sunxi-ng/ccu_nkmp.c
+++ b/drivers/clk/sunxi-ng/ccu_nkmp.c
@@ -32,40 +32,70 @@ static unsigned long ccu_nkmp_calc_rate(unsigned long parent,
 static unsigned long ccu_nkmp_find_best(unsigned long parent, unsigned long rate,
 					struct _ccu_nkmp *nkmp)
 {
+	unsigned long _k, _m, _p;
+	unsigned long max_p = rate >= 240000000 ? 1 : nkmp->max_p;
+	unsigned approx;
 	unsigned long best_rate = 0;
-	unsigned long best_n = 0, best_k = 0, best_m = 0, best_p = 0;
-	unsigned long _n, _k, _m, _p;
 
-	for (_k = nkmp->min_k; _k <= nkmp->max_k; _k++) {
-		for (_n = nkmp->min_n; _n <= nkmp->max_n; _n++) {
+	for (approx = 0; approx <= 1; approx++) {
+		for (_p = nkmp->min_p; _p <= max_p; _p <<= 1) {
 			for (_m = nkmp->min_m; _m <= nkmp->max_m; _m++) {
-				for (_p = nkmp->min_p; _p <= nkmp->max_p; _p <<= 1) {
-					unsigned long tmp_rate;
-
-					tmp_rate = ccu_nkmp_calc_rate(parent,
-								      _n, _k,
-								      _m, _p);
-
-					if (tmp_rate > rate)
-						continue;
-
-					if ((rate - tmp_rate) < (rate - best_rate)) {
-						best_rate = tmp_rate;
-						best_n = _n;
-						best_k = _k;
-						best_m = _m;
-						best_p = _p;
+				u64 nk = (u64)rate * _m * _p;
+				unsigned long nk_rem = do_div(nk, parent);
+
+				if (nk_rem != 0 && !approx)
+					continue;
+
+				if (nk < 10 || nk > 88)
+					continue;
+
+				for (_k = nkmp->min_k; _k <= nkmp->max_k; _k++) {
+					if (approx) {
+						u64 _n = (u64)rate * _m * _p;
+						unsigned long tmp_rate;
+
+						do_div(_n, parent * _k);
+
+						if (_n < nkmp->min_n || _n > nkmp->max_n)
+							continue;
+
+						tmp_rate = ccu_nkmp_calc_rate(parent,
+									      _n, _k,
+									      _m, _p);
+						if (tmp_rate > rate)
+							continue;
+
+						if ((rate - tmp_rate) < (rate - best_rate)) {
+							best_rate = tmp_rate;
+							nkmp->n = _n;
+							nkmp->k = _k;
+							nkmp->m = _m;
+							nkmp->p = _p;
+						}
+					} else {
+						u64 _n = nk;
+						unsigned long _n_rem = do_div(_n, _k);
+
+						if (_n < nkmp->min_n || _n > nkmp->max_n)
+							continue;
+
+						if (_n_rem == 0) {
+							nkmp->n = _n;
+							nkmp->k = _k;
+							nkmp->m = _m;
+							nkmp->p = _p;
+							return ccu_nkmp_calc_rate(parent,
+										  nkmp->n,
+										  nkmp->k,
+										  nkmp->m,
+										  nkmp->p);
+						}
 					}
 				}
 			}
 		}
 	}
 
-	nkmp->n = best_n;
-	nkmp->k = best_k;
-	nkmp->m = best_m;
-	nkmp->p = best_p;
-
 	return best_rate;
 }
 
-- 
2.54.0

Re: [PATCH] clk: sunxi-ng: Change NKMP algorithm for finding factors

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [High] Failure to initialize output struct fields in `ccu_nkmp_find_best` leads to writing stack garbage to hardware registers.
- [High] The new algorithm divides by the parent clock rate, leading to a kernel panic if the parent rate is 0.
- [High] Regression in rate clamping: the new algorithm fails to return the closest valid rate when the requested rate is outside the achievable bounds.
- [Medium] The new approximate rate search algorithm skips valid and better clock multipliers by only evaluating the truncated `_n`.
--

--- Patch [1]: [PATCH] clk: sunxi-ng: Change NKMP algorithm for finding factors ---
commit d6ad51cc524475bf9f5a9b1a358305bd319886bf
Author: Ondrej Jirman <megi@xff.cz>

clk: sunxi-ng: Change NKMP algorithm for finding factors

This patch optimizes the NKMP algorithm for finding clock factors by reducing 
unnecessary iterations. It introduces an approach that respects physical SoC 
restrictions and avoids brute-forcing all possibilities.

> diff --git a/drivers/clk/sunxi-ng/ccu_nkmp.c b/drivers/clk/sunxi-ng/ccu_nkmp.c
> index 25efb5b376075..c39b198914316 100644
> --- a/drivers/clk/sunxi-ng/ccu_nkmp.c
> +++ b/drivers/clk/sunxi-ng/ccu_nkmp.c

[ ... ]

> @@ -32,40 +32,70 @@ static unsigned long ccu_nkmp_calc_rate(unsigned long parent,
>  static unsigned long ccu_nkmp_find_best(unsigned long parent, unsigned long rate,
>  					struct _ccu_nkmp *nkmp)
>  {
> +	unsigned long _k, _m, _p;
> +	unsigned long max_p = rate >= 240000000 ? 1 : nkmp->max_p;
> +	unsigned approx;
>  	unsigned long best_rate = 0;

[ ... ]

> +	for (approx = 0; approx <= 1; approx++) {
> +		for (_p = nkmp->min_p; _p <= max_p; _p <<= 1) {
>  			for (_m = nkmp->min_m; _m <= nkmp->max_m; _m++) {
> +				u64 nk = (u64)rate * _m * _p;
> +				unsigned long nk_rem = do_div(nk, parent);

[Severity: High]
Does this code handle the case where parent is 0?

In the Linux clock framework, an orphaned clock or one with an absent parent
will have a parent rate of 0. Performing a division on such a clock will
trigger a division-by-zero hardware exception here.

> +
> +				if (nk_rem != 0 && !approx)
> +					continue;
> +
> +				if (nk < 10 || nk > 88)
> +					continue;
> +
> +				for (_k = nkmp->min_k; _k <= nkmp->max_k; _k++) {
> +					if (approx) {
> +						u64 _n = (u64)rate * _m * _p;
> +						unsigned long tmp_rate;
> +
> +						do_div(_n, parent * _k);

[Severity: High]
Can parent * _k evaluate to 0 if parent is 0, leading to a division-by-zero
exception here as well?

[Severity: Medium]
Will calculating _n via integer division skip valid and better multipliers?

Because the target rate is often already truncated by a previous round rate
operation, calculating _n analytically can yield an _n that is exactly 1 less
than the optimal value. By failing to check _n + 1, this logic could lock in
a suboptimal configuration.

> +
> +						if (_n < nkmp->min_n || _n > nkmp->max_n)
> +							continue;

[Severity: High]
Is it intended to silently skip configurations that exceed hardware bounds
instead of clamping to nkmp->max_n?

When drivers request an unachievably high clock rate to configure a clock
to its physical maximum, this logic explicitly rejects the out-of-bounds _n.

This results in the function finding zero valid configurations and returning
a rate of 0, which breaks clock initialization for drivers relying on standard
maximum-rate clamping behavior.

> +
> +						tmp_rate = ccu_nkmp_calc_rate(parent,
> +									      _n, _k,

[ ... ]

> -	nkmp->n = best_n;
> -	nkmp->k = best_k;
> -	nkmp->m = best_m;
> -	nkmp->p = best_p;
> -
>  	return best_rate;
>  }

[Severity: High]
If a valid combination cannot be found, could this return 0 without
initializing the nkmp fields?

If the clock framework calls ccu_nkmp_set_rate() with a rate that cannot
be satisfied, returning 0 leaves the multiplier and divider fields as
uninitialized stack variables.

These random stack values are then shifted and written directly into the
hardware clock configuration registers:

drivers/clk/sunxi-ng/ccu_nkmp.c:ccu_nkmp_set_rate() {
    ...
    reg |= ((_nkmp.n - nkmp->n.offset) << nkmp->n.shift) & n_mask;
    reg |= ((_nkmp.k - nkmp->k.offset) << nkmp->k.shift) & k_mask;
    reg |= ((_nkmp.m - nkmp->m.offset) << nkmp->m.shift) & m_mask;
    reg |= (ilog2(_nkmp.p) << nkmp->p.shift) & p_mask;
    ...
}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260725122645.2270876-1-megi@xff.cz?part=1