<p>Nico Huber has uploaded this change for <strong>review</strong>.</p><p><a href="https://review.coreboot.org/21915">View Change</a></p><pre style="font-family: monospace,monospace; white-space: pre-wrap;">[WIP] cpu/x86/mtrr: Optimize hole carving strategy<br><br>For WB ranges with unaligned end, we try to align the range up and<br>carve a hole out of it which might reduce MTRR usage. Instead of<br>trying an arbitrary alignment, we choose an optimal one.<br><br>Change-Id: Iefb064ce8c4f293490a19dd46054b966c63bde44<br>Signed-off-by: Nico Huber <nico.h@gmx.de><br>---<br>M src/cpu/x86/mtrr/mtrr.c<br>1 file changed, 84 insertions(+), 25 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">git pull ssh://review.coreboot.org:29418/coreboot refs/changes/15/21915/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 c2c629c..82666fc 100644<br>--- a/src/cpu/x86/mtrr/mtrr.c<br>+++ b/src/cpu/x86/mtrr/mtrr.c<br>@@ -105,8 +105,6 @@<br> #define RANGE_TO_PHYS_ADDR(x) (((resource_t)(x)) << RANGE_SHIFT)<br> #define NUM_FIXED_MTRRS (NUM_FIXED_RANGES / RANGES_PER_FIXED_MTRR)<br> <br>-/* The minimum alignment while handling variable MTRR ranges is 64MiB. */<br>-#define MTRR_MIN_ALIGN PHYS_TO_RANGE_ADDR(64 << 20)<br> /* Helpful constants. */<br> #define RANGE_1MB PHYS_TO_RANGE_ADDR(1 << 20)<br> #define RANGE_4GB (1 << (ADDR_SHIFT_TO_RANGE_SHIFT(32)))<br>@@ -471,10 +469,63 @@<br> }<br> }<br> <br>+static uint32_t optimize_var_mtrr_hole(const uint32_t base,<br>+ const uint32_t limit)<br>+{<br>+ /*<br>+ * With default type UC, we can potentially optimize a WB<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 predict<br>+ * how many MTRRs calc_var_mtrr_range() will spend for the<br>+ * hole and how many it will save us for the original range.<br>+ *<br>+ * We take two parameters, the upper end of the WB range as<br>+ * `base` of the hole and a `limit` how far we may align it<br>+ * up. As long as `base` is unaligned, calc_var_mtrr_range()<br>+ * would add MTRRs of the size of lowest significant bit set<br>+ * in `base` and add that size to `base`.<br>+ *<br>+ * We don't have to exercise all these additions. As we know<br>+ * the next MTRR to set will be at the position the carry of<br>+ * last addition takes. That is the closest 0 in a more sig-<br>+ * nificant position. So we account one MTRR for the least<br>+ * signifcant bit set in `base` plus one for each unset bit<br>+ * up to the new alignment.<br>+ *<br>+ * OTOH, for every bit that is flipped to zero in `base` due<br>+ * to the alignment, we save one MTRR for the original WB<br>+ * range. Minus one for the final carry bit.<br>+ */<br>+<br>+ int gain = -2; /* Minus one for the first addition and<br>+ minus one for the final carry bit. */<br>+ int best_gain = 0;<br>+ uint32_t bit, best_bit = 1;<br>+ const uint32_t last_bit = 1 << fms(base);<br>+<br>+ /* Count 1s that will flip as gain, 0s we have to force as loss. */<br>+ for (bit = 1 << fls(base); bit <= last_bit; bit <<= 1) {<br>+ if (ALIGN_UP(base, bit) > limit)<br>+ break;<br>+ if (base & bit) {<br>+ if (++gain > best_gain) {<br>+ best_gain = gain;<br>+ best_bit = bit;<br>+ }<br>+ } else {<br>+ --gain;<br>+ }<br>+ }<br>+<br>+ return ALIGN_UP(base, best_bit);<br>+}<br>+<br> static void calc_var_mtrrs_with_hole(struct var_mtrr_state *var_state,<br> struct range_entry *r)<br> {<br>- uint32_t a1, a2, b1, b2;<br>+ uint32_t a1, a2, b1, b2, b2_limit;<br> int mtrr_type;<br> struct range_entry *next;<br> <br>@@ -482,11 +533,11 @@<br> * Determine MTRRs based on the following algorithm for the given entry:<br> * +------------------+ b2 = ALIGN_UP(end)<br> * | 0 or more bytes | <-- hole is carved out between b1 and b2<br>- * +------------------+ a2 = b1 = end<br>+ * +------------------+ a2 = b1 = original end<br> * | |<br> * +------------------+ a1 = begin<br> *<br>- * Thus, there are 3 sub-ranges to configure variable MTRRs for.<br>+ * Thus, there are up to 2 sub-ranges to configure variable MTRRs for.<br> */<br> mtrr_type = range_entry_mtrr_type(r);<br> <br>@@ -513,38 +564,46 @@<br> if (!var_state->above4gb && a2 > RANGE_4GB)<br> a2 = RANGE_4GB;<br> <br>+ /* May carve out hole if type is WB, otherwise we are done. */<br>+ if (mtrr_type != MTRR_TYPE_WRBACK) {<br>+ calc_var_mtrr_range(var_state, a1, a2 - a1, mtrr_type);<br>+ return;<br>+ }<br>+<br> next = memranges_next_entry(var_state->addr_space, r);<br> <br> b1 = a2;<br> <br> /* First check if a1 is >= 4GiB and the current entry is the last<br> * entry. If so perform an optimization of covering a larger range<br>- * defined by the base address' alignment. */<br>+ * by aligning up, at most to the next power of 2. */<br> if (a1 >= RANGE_4GB && next == NULL) {<br>- uint32_t addr_lsb;<br>+ uint32_t align;<br> <br>- addr_lsb = fls(a1);<br>- b2 = (1 << addr_lsb) + a1;<br>- if (b2 >= a2) {<br>- calc_var_mtrr_range(var_state, a1, b2 - a1, mtrr_type);<br>- return;<br>- }<br>- }<br>+ /* Find first alignment that doesn't overflow. */<br>+ align = 1 << fms(a2);<br>+ do {<br>+ b2 = ALIGN_UP(a2, align);<br>+ align >>= 1;<br>+ } while (b2 < a2);<br> <br>- /* Handle the min alignment roundup case. */<br>- b2 = ALIGN_UP(a2, MTRR_MIN_ALIGN);<br>-<br>- /* Check against the next range. If the current range_entry is the<br>- * last entry then carving a hole is no problem. If the current entry<br>- * isn't the last entry then check that the last entry covers the<br>- * entire hole range with the default mtrr type. */<br>- if (next != NULL &&<br>- (range_entry_mtrr_type(next) != var_state->def_mtrr_type ||<br>- range_entry_end_mtrr_addr(next) < b2)) {<br>- calc_var_mtrr_range(var_state, a1, a2 - a1, mtrr_type);<br>+ calc_var_mtrr_range(var_state, a1, b2 - a1, mtrr_type);<br> return;<br> }<br> <br>+ /* Find the limit how far we may align up. */<br>+ if (next == NULL) {<br>+ b2_limit = ALIGN_UP(a2, 1 << fms(a2));<br>+ } else if (range_entry_mtrr_type(next) == var_state->def_mtrr_type) {<br>+ b2_limit = range_entry_end_mtrr_addr(next);<br>+ } else {<br>+ b2_limit = a2;<br>+ }<br>+ /* No bits above a1's alignment may change, it would double the cost. */<br>+ if (a1)<br>+ b2_limit = MIN(ALIGN_UP(a2 + 1, 1 << fls(a1)) - 1, b2_limit);<br>+ b2 = optimize_var_mtrr_hole(a2, b2_limit);<br>+<br> calc_var_mtrr_range(var_state, a1, b2 - a1, mtrr_type);<br> calc_var_mtrr_range(var_state, b1, b2 - b1, var_state->def_mtrr_type);<br> }<br></pre><p>To view, visit <a href="https://review.coreboot.org/21915">change 21915</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/21915"/><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: Iefb064ce8c4f293490a19dd46054b966c63bde44 </div>
<div style="display:none"> Gerrit-Change-Number: 21915 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: Nico Huber <nico.h@gmx.de> </div>