How to iterate over MTRRs

[nullplan]

Hello everyone,

I have been told not to use hugepage maps if they cover multiple memory types. That is very sensible, of course, but it does put the burden on me to actually check this. Since my current approach is to just map everything as writeback memory, only MTRRs could make it nonconsistent. Since I am a very top-down thinker, I just decomposed the problem. So we are given a physical address and a length, and have to make sure the whole range has the same memtype. OK, easy enough to conceptualize:

Code: Select all

static bool is_range_memtype_consistent(phys_addr_t addr, size_t len)
{
  phys_addr_t end = addr + len;
  int t = query_memtype(addr);
  while ((addr = next_region(addr)) < end)
    if (query_memtype(addr) != t) return false;
  return true;
}

And query_memtype is also easy enough to write: If fixed MTRRs are supported and address is below 1MB, query the appropriate fixed MTRR, else check all the variable ones to find if one fits, else return the default type. But next_region() is becoming a bit of a hedgehog in my prostate. So what it is supposed to do is find out which MTRR governs the input address and return the smallest address governed by a different MTRR (field). For the fixed range, this is simple. For the variable MTRRs, this is a bit of a wobble, since we are given those as pairs of masks and values. If the given address fits into a variable MTRR, finding the next address outside of it is simply done by adding the least significant set bit of the mask to the input address and then clearing all address bits lower than that. That definitely gives us the first address larger than the input address outside of the current MTRR.

But the problem is the last remaining case: If I have an address that is not part of any MTRR, how do I find at least halfway quickly the next address inside of some MTRR? Or even figure out that there are no other MTRRs left? If the variable MTRRs were given as base addresses and lengths, this would be easy, but they are not. The masks can have holes in them. I don't know why anyone would use a striped MTRR setup, but BIOS writers can be weird people.

Maybe I ought to deconstruct the problem into a smaller one. Given an input, a mask, and a value, the fact that (value & ~mask) == 0 (because if that is not true, the MTRR is effectively disabled, and I just filter that at initialization time), and the fact that (input & mask) != value, what is the smallest x such that ((input + x) & mask) == value? If I can solve that problem, I can iterate over all variable MTRRs, figure out for which one I get the smallest x, and return that. Thankfully, we don't need to handle the case where x does not exist, because the addition is allowed to overflow, and if it does, the addend will be bigger than for any non-overflowing one. So I can filter out the overflows at the end of the function and return the highest physical address in that case.

I get the feeling I need to look at (input & mask) ^ value, the mask of differences. But not all differences are the same! Again, I see two possibilities: If an input bit is 0 but needs to be 1, I can just set that bit in x, but if the bit is 1 and needs to be 0, setting the bit in x will cause a carry-out in the addition. Which can cause more differences. Does anyone have an idea here? Or am I way overthinking it and should just query the memtype for all pages in the range?

[linuxyne]

Some under-cooked thoughts:

Assuming 32-bit physical addresses (no pae, no long mode, etc.)

If the mask is 0xf9000000 (this creates holes), then consider only the zeroes which lie towards the left of the LSB that is 1.
In the below figure, the LSB that is 1 is at bit position 24 (counting from 0), so consider the zeroes at bit positions 25 and 26.

Code: Select all

3322 2222 2222 1111 1111 1100 0000 0000
1098 7654 3210 9876 5432 1098 7654 3210
---------------------------------------------------
1111 1001 0000 0000 0000 0000 0000 0000

# These 4 range-sets, when ANDed with the mask 0xf9000000, will output the same result, for a given choice of g, h, i, j, k and m bits.

ghij k00m ....
ghij k01m ....
ghij k10m ....
ghij k11m ....

Suppose we choose the base address with bits 25 and 26 to be 0 (to simplify matters):

Code: Select all

ghij k..m ....
-------------
1011 1001 ....

That corresponds to base 0xb9000000. These ranges are mapped:

Code: Select all

[0xb9000000, 0xb9fffffff] (corresponding to 1011 1001 ....)
[0xbb000000, 0xbbfffffff] (corresponding to 1011 1011 ....)
[0xbd000000, 0xbdfffffff] (corresponding to 1011 1101 ....)
[0xbf000000, 0xbffffffff] (corresponding to 1011 1111 ....)

The size of the mapping is exactly -0xf9000000 = 0x7000000. (Note that the last unmapped region, beginning at 0xc0000000, is ignored).

Thus, the # of mapped regions in a discontinuous range is equal to 2^a where a == # of zeros in the mask left to the LSB that is 1, assuming that the base address is approriately chosen, else it may be less. The base address choice which results in the largest possible region is when all those zero-positions (which are left to the LSB that is 1 in the mask) are kept as zero.

The total size of the region is -mask, when ignoring the size of the last unmapped region of the MTRR, and when assuming that the base address chosen is one of the "natural" base addresses for the given mask.

This should help in creating an array of base, size of the mappings (multiple such maps per MTRR if there are discontinuous regions in an MTRR). Then the "MTRR Precedences" can be applied, range intersection can be performed, etc.

[Octocontrabass]

It sounds like you want a memory map, but for memory types. So why not make one? Build a list with ranges for each MTRR, combine overlaps according to their effective type, and merge adjacent regions of the same type. You can even add the fixed MTRRs and the default memory type to your list.

But maybe you still want to decide the memory type using only the MTRRs. Take advantage of the fact that the page size is always a power of 2 and naturally aligned: first check the upper bits of each variable MTRR to see if it applies to any part of the page you're trying to create, and if it does, check the lower bits to see if the MTRR applies to the whole page or only parts of it. To deal with partial MTRR coverage, you either need a clever algorithm or a brute-force search, but I'm not feeling clever enough at the moment to come up with a good algorithm...