Skip to contentSkip to conversation

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

PATCH In review Ondřej Jirman 2 participants 3 messages Jul 25 – Jul 29

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 clk: sunxi-ng: Change NKMP algorithm for finding factors

From: Ondrej Jirman <[email protected]>

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.

---
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(-)
drivers/clk/sunxi-ng/ccu_nkmp.c +55 -25
index 25efb5b37607..c39b19891431 100644
@@ -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;
 }
 
Signature · 1 line
2.54.0
#1 lore raw
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…

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 <[email protected]>

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.

Quoted 4 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +0 -0
index 25efb5b376075..c39b198914316 100644

[ ... ]

Quoted 8 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +3 -0
@@ -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;

[ ... ]

drivers/clk/sunxi-ng/ccu_nkmp.c static unsigned long ccu_nkmp_calc_rate(unsigned long parent, · line 44

Quoted 5 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +4 -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.

drivers/clk/sunxi-ng/ccu_nkmp.c static unsigned long ccu_nkmp_calc_rate(unsigned long parent, · line 57

Quoted 13 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +13 -0
+
+				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.

drivers/clk/sunxi-ng/ccu_nkmp.c static unsigned long ccu_nkmp_calc_rate(unsigned long parent, · line 60

Quoted 3 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +3 -0
+
+						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.

Quoted 3 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +3 -0
+
+						tmp_rate = ccu_nkmp_calc_rate(parent,
+									      _n, _k,

[ ... ]

drivers/clk/sunxi-ng/ccu_nkmp.c static unsigned long ccu_nkmp_calc_rate(unsigned long parent, · line 100

Quoted 7 lines
drivers/clk/sunxi-ng/ccu_nkmp.c +0 -5
-	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;
    ...
}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#2 lore raw
In reply to Ondřej Jirman
Quoted 20 lines · megi xff

From: Ondrej Jirman <[email protected]>

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.

Quoted 6 lines

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.

I withdraw this patch. I reworked it with clock specific settings for these PLL specific constraints (instead of hardcoding) and I'll run the new version for a while before submitting again.

Best regards,

	o.
Quoted 118 lines

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.

---
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(-)
drivers/clk/sunxi-ng/ccu_nkmp.c +55 -25
index 25efb5b37607..c39b19891431 100644
@@ -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;
 }
 
Signature · 1 line
2.54.0