<p>Nico Huber has uploaded this change for <strong>review</strong>.</p><p><a href="https://review.coreboot.org/22119">View Change</a></p><pre style="font-family: monospace,monospace; white-space: pre-wrap;">cpu/x86/mtrr: Optimize optimize_var_mtrr_hole()<br><br>This alternative implementation reduces runtime complexity a lot. But<br>as numbers are small, it only gains us about 1us. Also, the original<br>implementation is more explicit about what is done.<br><br>Change-Id: Idcdc0f3a4cc9be8592454bf977feb99deb0f529e<br>Signed-off-by: Nico Huber <nico.h@gmx.de><br>---<br>M src/cpu/x86/mtrr/mtrr.c<br>1 file changed, 38 insertions(+), 27 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">git pull ssh://review.coreboot.org:29418/coreboot refs/changes/19/22119/1</pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">diff --git a/src/cpu/x86/mtrr/mtrr.c b/src/cpu/x86/mtrr/mtrr.c<br>index 6f1aef0..6bcc8c0 100644<br>--- a/src/cpu/x86/mtrr/mtrr.c<br>+++ b/src/cpu/x86/mtrr/mtrr.c<br>@@ -457,8 +457,7 @@<br> }<br> }<br> <br>-static uint32_t optimize_var_mtrr_hole(struct var_mtrr_state *const var_state,<br>- const uint32_t base,<br>+static uint32_t optimize_var_mtrr_hole(const uint32_t base,<br> const uint32_t hole,<br> const uint64_t limit,<br> const int carve_hole)<br>@@ -468,7 +467,7 @@<br> * range with unaligned upper end, by aligning it up and<br> * carving the added "hole" out again.<br> *<br>- * To optimize the upper end of the hole, we will test<br>+ * To optimize the upper end of the hole, we will predict<br> * how many MTRRs calc_var_mtrr_range() will spend for any<br> * alignment of the hole's upper end.<br> *<br>@@ -479,34 +478,47 @@<br> * for carving the hole out. We return the optimal upper end<br> * for the hole (which may be the same as the end of the WB<br> * range in case we don't gain anything by aligning up).<br>+ *<br>+ * We don't have to exercise all the MTRR calculations for<br>+ * each alignment. Instead, we can predict the gain (and loss)<br>+ * for each alignment by looking at the bit pattern in `hole`.<br>+ * Every time we align further up, one or more bits will flip<br>+ * to `0`. We save one MTRR for each cleared bit for the en-<br>+ * larged WB range. OTOH, for every `0` bit in the pattern,<br>+ * we have to spend one MTRR to carve the hole out.<br>+ *<br>+ * Last but not least, we'd have to spend an additional MTRR<br>+ * for each bit flipped above the biggest MTRR entry that<br>+ * calc_var_mtrr_range(base, hole - base) implies. So we won't<br>+ * try any bits above that alignment at all.<br> */<br> <br>- unsigned int align, best_count;<br>+ /* The minimum `base` has to be aligned up to during MTRR filling. */<br>+ const int minimum_alignment = MAX(fms(~base & hole), fls(base));<br>+<br>+ /* The final carry bit, capped by `minimum_alignment`. */<br>+ const int final = MIN(fms(hole) + 1, minimum_alignment);<br>+ /* We start search at the least significant bit in `hole`. */<br>+ const int first = fls(hole);<br>+<br>+ /* Get us started by forcing the first bit. */<br>+ uint64_t hole_end = hole + (1 << first);<br>+<br>+ /* Start gain, account for the first addition. */<br>+ int gain = -carve_hole;<br>+ int best_gain = 0, bit;<br> uint32_t best_end = hole;<br> <br>- /* calculate MTRR count for the WB range alone (w/o a hole) */<br>- calc_var_mtrr_range(var_state, base, hole - base, MTRR_TYPE_WRBACK);<br>- best_count = var_state->mtrr_index;<br>- var_state->mtrr_index = 0;<br>-<br>- for (align = fls(hole) + 1; align <= fms(hole) + 1; ++align) {<br>- const uint32_t hole_end = ALIGN_UP(hole, 1 << align);<br>- if (hole_end > limit)<br>- break;<br>-<br>- /* calculate MTRR count for this alignment */<br>- calc_var_mtrr_range(var_state,<br>- base, hole_end - base, MTRR_TYPE_WRBACK);<br>- if (carve_hole) {<br>- calc_var_mtrr_range(var_state, hole, hole_end - hole,<br>- MTRR_TYPE_UNCACHEABLE);<br>- }<br>-<br>- if (var_state->mtrr_index < best_count) {<br>- best_count = var_state->mtrr_index;<br>+ /* Count 1s that will flip as gain, 0s we have to force as loss. */<br>+ for (bit = first + 1; bit < final && hole_end <= limit; ++bit) {<br>+ if (!(hole & 1 << bit)) {<br>+ /* Have to force a 0 to 1. */<br>+ hole_end += 1 << bit;<br>+ gain -= carve_hole;<br>+ } else if (++gain > best_gain) {<br>+ best_gain = gain;<br> best_end = hole_end;<br> }<br>- var_state->mtrr_index = 0;<br> }<br> <br> return best_end;<br>@@ -596,8 +608,7 @@<br> b2_limit = range_entry_base_mtrr_addr(next);<br> carve_hole = 1;<br> }<br>- b2 = optimize_var_mtrr_hole(<br>- var_state, a1, b1, b2_limit, carve_hole);<br>+ b2 = optimize_var_mtrr_hole(a1, b1, b2_limit, carve_hole);<br> }<br> <br> calc_var_mtrr_range(var_state, a1, b2 - a1, mtrr_type);<br></pre><p>To view, visit <a href="https://review.coreboot.org/22119">change 22119</a>. To unsubscribe, visit <a href="https://review.coreboot.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://review.coreboot.org/22119"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: coreboot </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-MessageType: newchange </div>
<div style="display:none"> Gerrit-Change-Id: Idcdc0f3a4cc9be8592454bf977feb99deb0f529e </div>
<div style="display:none"> Gerrit-Change-Number: 22119 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: Nico Huber <nico.h@gmx.de> </div>