[coreboot-gerrit] Change in coreboot[master]: cpu/x86/mtrr: Optimize optimize_var_mtrr_hole()

[Nico Huber (Code Review)]

Nico Huber has uploaded this change for review. ( https://review.coreboot.org/22119


Change subject: cpu/x86/mtrr: Optimize optimize_var_mtrr_hole()
......................................................................

cpu/x86/mtrr: Optimize optimize_var_mtrr_hole()

This alternative implementation reduces runtime complexity a lot. But
as numbers are small, it only gains us about 1us. Also, the original
implementation is more explicit about what is done.

Change-Id: Idcdc0f3a4cc9be8592454bf977feb99deb0f529e
Signed-off-by: Nico Huber <nico.h at gmx.de>
---
M src/cpu/x86/mtrr/mtrr.c
1 file changed, 38 insertions(+), 27 deletions(-)



  git pull ssh://review.coreboot.org:29418/coreboot refs/changes/19/22119/1

diff --git a/src/cpu/x86/mtrr/mtrr.c b/src/cpu/x86/mtrr/mtrr.c
index 6f1aef0..6bcc8c0 100644
--- a/src/cpu/x86/mtrr/mtrr.c
+++ b/src/cpu/x86/mtrr/mtrr.c
@@ -457,8 +457,7 @@
 	}
 }
 
-static uint32_t optimize_var_mtrr_hole(struct var_mtrr_state *const var_state,
-				       const uint32_t base,
+static uint32_t optimize_var_mtrr_hole(const uint32_t base,
 				       const uint32_t hole,
 				       const uint64_t limit,
 				       const int carve_hole)
@@ -468,7 +467,7 @@
 	 * range with unaligned upper end, by aligning it up and
 	 * carving the added "hole" out again.
 	 *
-	 * To optimize the upper end of the hole, we will test
+	 * To optimize the upper end of the hole, we will predict
 	 * how many MTRRs calc_var_mtrr_range() will spend for any
 	 * alignment of the hole's upper end.
 	 *
@@ -479,34 +478,47 @@
 	 * for carving the hole out. We return the optimal upper end
 	 * for the hole (which may be the same as the end of the WB
 	 * range in case we don't gain anything by aligning up).
+	 *
+	 * We don't have to exercise all the MTRR calculations for
+	 * each alignment. Instead, we can predict the gain (and loss)
+	 * for each alignment by looking at the bit pattern in `hole`.
+	 * Every time we align further up, one or more bits will flip
+	 * to `0`. We save one MTRR for each cleared bit for the en-
+	 * larged WB range. OTOH, for every `0` bit in the pattern,
+	 * we have to spend one MTRR to carve the hole out.
+	 *
+	 * Last but not least, we'd have to spend an additional MTRR
+	 * for each bit flipped above the biggest MTRR entry that
+	 * calc_var_mtrr_range(base, hole - base) implies. So we won't
+	 * try any bits above that alignment at all.
 	 */
 
-	unsigned int align, best_count;
+	/* The minimum `base` has to be aligned up to during MTRR filling. */
+	const int minimum_alignment = MAX(fms(~base & hole), fls(base));
+
+	/* The final carry bit, capped by `minimum_alignment`. */
+	const int final = MIN(fms(hole) + 1, minimum_alignment);
+	/* We start search at the least significant bit in `hole`. */
+	const int first = fls(hole);
+
+	/* Get us started by forcing the first bit. */
+	uint64_t hole_end = hole + (1 << first);
+
+	/* Start gain, account for the first addition. */
+	int gain = -carve_hole;
+	int best_gain = 0, bit;
 	uint32_t best_end = hole;
 
-	/* calculate MTRR count for the WB range alone (w/o a hole) */
-	calc_var_mtrr_range(var_state, base, hole - base, MTRR_TYPE_WRBACK);
-	best_count = var_state->mtrr_index;
-	var_state->mtrr_index = 0;
-
-	for (align = fls(hole) + 1; align <= fms(hole) + 1; ++align) {
-		const uint32_t hole_end = ALIGN_UP(hole, 1 << align);
-		if (hole_end > limit)
-			break;
-
-		/* calculate MTRR count for this alignment */
-		calc_var_mtrr_range(var_state,
-				base, hole_end - base, MTRR_TYPE_WRBACK);
-		if (carve_hole) {
-			calc_var_mtrr_range(var_state, hole, hole_end - hole,
-					    MTRR_TYPE_UNCACHEABLE);
-		}
-
-		if (var_state->mtrr_index < best_count) {
-			best_count = var_state->mtrr_index;
+	/* Count 1s that will flip as gain, 0s we have to force as loss. */
+	for (bit = first + 1; bit < final && hole_end <= limit; ++bit) {
+		if (!(hole & 1 << bit)) {
+			/* Have to force a 0 to 1. */
+			hole_end += 1 << bit;
+			gain -= carve_hole;
+		} else if (++gain > best_gain) {
+			best_gain = gain;
 			best_end = hole_end;
 		}
-		var_state->mtrr_index = 0;
 	}
 
 	return best_end;
@@ -596,8 +608,7 @@
 			b2_limit = range_entry_base_mtrr_addr(next);
 			carve_hole = 1;
 		}
-		b2 = optimize_var_mtrr_hole(
-				var_state, a1, b1, b2_limit, carve_hole);
+		b2 = optimize_var_mtrr_hole(a1, b1, b2_limit, carve_hole);
 	}
 
 	calc_var_mtrr_range(var_state, a1, b2 - a1, mtrr_type);

-- 
To view, visit https://review.coreboot.org/22119
To unsubscribe, visit https://review.coreboot.org/settings

Gerrit-Project: coreboot
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Idcdc0f3a4cc9be8592454bf977feb99deb0f529e
Gerrit-Change-Number: 22119
Gerrit-PatchSet: 1
Gerrit-Owner: Nico Huber <nico.h at gmx.de>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.coreboot.org/pipermail/coreboot-gerrit/attachments/20171020/b4b21464/attachment.html>