New memory map structure

[Antti]

Code: Select all

MEMORY MAP ENTRY

BITS  63....4   3 2 1 0
      |_____|   |_____|
            |         |_____________ MEMORY TYPE BITS
            |
            |_______________________ START ADDRESS BITS

MEMORY MAP

  MEMORY MAP ENTRY (highest start address)
  ...
  ...
  ...
  MEMORY MAP ENTRY (start address zero, end of memory map)

What do you think? I am sure that someone has already used this (but I have not seen yet). This simple structure describes the whole address space (no gaps) and does not care where the memory information is from (BIOS or UEFI). If we have a memory address and we need to check what the type is, we just go through the list and pick up the first entry that is equal or less.

Note that memory type bits mean alignment restrictions but I do not think it is a problem. Theoretically we might lose some usable memory (it is safe) but a real problem is whether 4 bits is enough or not for describing the type. Perhaps memory bits could be extensible, i.e. using more bits if bit 3 is set or something like that.

[bwat]

[Deleted as I don't think I understand what you're describing]

[embryo]

What do you think?

I think that any structure can be used. Advantages can be found almost in every structure. Your structure seems is optimized for 8 byte machine word, but it is not the only possible optimization target.

It is better to state your goal clearly, next goes goal achievement strategy, and then goes design, followed by implementation. And this loop should be performed for every goal in the tree of goals you can build from something called "root" goal. If the root goal is an OS, then memory map structure lies somewhere in the very depth of the tree and should be approached only after higher level goals are understood and the achievement strategy is elaborated for every such goal.

But in case of doing osdeving just for fun and learning it is not very important to have an optimal structure. You can have any structure and then just start working with it - the advantages and disadvantages will come quickly to you almost automagically.

[Antti]

it is not very important to have an optimal structure

I wanted to have a good structure. Now it seems that it is also quite optimal but that is not the most important thing. This structure requires to have a memory map that describes the whole address space. There is also only one correct order.

Important addition: the same start address is allowed to be used once.

[sortie]

It is probably safe to even require the entries to be page aligned. Indeed, that would make code using it potentially simpler if it deals with paging. On x86_64 that would mean the bottom 12 bits are available for use (perhaps even some top bits, too).

[Antti]

Code: Select all

MEMORY MAP ENTRY (4-bit type)

BITS  63....4   3 2 1 0
      |_____|   |_____|
            |         |_____________ MEMORY TYPE BITS (except 0000b and 1111b)
            |
            |_______________________ START ADDRESS BITS [63:4]



MEMORY MAP ENTRY (8-bit type)

BITS  63...12   11....4   3 2 1 0
      |_____|   |_____|   |_____|
            |         |         |___ ALL BITS SET (1111b)
            |         |
            |         |_____________ MEMORY TYPE BITS (except 11111111b)
            |
            |_______________________ START ADDRESS BITS [63:12]



MEMORY MAP ENTRY (unknown type)

BITS  63...12   11....4   3 2 1 0
      |_____|   |_____|   |_____|
            |         |         |___ ALL BITS SET (1111b)
            |         |
            |         |_____________ ALL BITS SET (11111111b)
            |
            |_______________________ UNKNOWN BITS [63:12]


Notes:
      - If bits [3:0] are all unset (0000b), an entry is not valid.
      - Unknown type entries are valid but skipped.

[Antti]

An unknown type entry is a problem! It is not an unknown type but just "unknown". It cannot be used as a type.

[Owen]

I have to ask: What is wrong with the UEFI memory map format? They even give you 2 billion types to use for your own purposes!

[Brendan]

Hi,

For 80x86, a physical address is (a maximum of) only 56 bits, and (assuming 4 Kib minimum alignment) that gives you a total of 20 bits you can use.

I like to combine all the information that's scattered everywhere into a single physical address space map. This information is:

• the address, size and type (from "int 0x15, eax=0xE820" or UEFI). Note: This involves merging the "extended attributes" that were introduced in ACPI 4.0 with the raw type you get from "int 0x15, eax=0xE820"; and converting both BIOS and UEFI's different memory types into a consistent set of types for the OS (which should probably be neither BIOS nor UEFI's types).
• Which NUMA domain the area is in (from ACPI's SRAT table)
• If the area is used for hot-plug RAM, including "unused, but reserved for hot-add RAM" and "usable RAM, that supports hot-remove" (also from ACPI's SRAT table)
• A "currently being removed or added" flag, and an "online or offline" flag, to keep track of hot-add and hot-remove transitions (there's several states - e.g. present and online, present and offline, currently being removed and removed)
• Cachability (write-back, write-through, write-combining, uncached, etc), which is given to you by UEFI's "GetMemoryMap()" but needs to be extracted from MTRRs if you booted from BIOS
• For memory mapped devices; some way of determining which device it is (e.g. for PCI devices a "bus:device:function" identifier)

Cheers,

Brendan

[Antti]

Brendan mentioned things that I have not thought. The only thing I can say is that I may have underestimated the information needed. It is better to design a format that is extensible enough. I was aware of 56 bits limit but it felt more natural to store address as a 64-bit number and "mask" lower bits.

I have to ask: What is wrong with the UEFI memory map format?

It has a length, NumberOfPages. I think that is wrong. I want to have a map that covers everything "by design".

[Owen]

Brendan mentioned things that I have not thought. The only thing I can say is that I may have underestimated the information needed. It is better to design a format that is extensible enough. I was aware of 56 bits limit but it felt more natural to store address as a 64-bit number and "mask" lower bits.

I have to ask: What is wrong with the UEFI memory map format?

It has a length, NumberOfPages. I think that is wrong. I want to have a map that covers everything "by design".

But that ignores the fact that much of the physical address space is not "memory", is not "reserved", is not "used"... but is nothing

You can convert either format to the other. Why does it matter which when the first thing you're going to do with it is shove it into some actually useful data structure?

[Antti]

Why does it matter which when the first thing you're going to do with it is shove it into some actually useful data structure?

So it does not make sense if my BIOS and UEFI boot loaders give a memory map that is uniform, compact, and is already verified to be correct? Is it better that my system checked those BIOS/UEFI-specific things after boot loaders? Or is it better that I create those "useful data structures" while still running boot loaders and make the decision of what is a useful data structure?

[Owen]

Why does it matter which when the first thing you're going to do with it is shove it into some actually useful data structure?

So it does not make sense if my BIOS and UEFI boot loaders give a memory map that is uniform, compact, and is already verified to be correct?

That makes perfect sense. (Well, except for checking the UEFI memory map. A UEFI implementation which gives you a bad memory map is serious trouble of the nothing can possibly work variety)

Is it better that my system checked those BIOS/UEFI-specific things after boot loaders? Or is it better that I create those "useful data structures" while still running boot loaders and make the decision of what is a useful data structure?

A "Useful data structure" probably doesn't look like a flat array. After all, they are terrible for resizing, etc, which undoubtedly your kernel is going to have to do whenever it needs to update the memory map ("I mapped PCI device 1.2.5 BAR 0 here")

So why invent something new and perfect?
Why not pick something that already exists and just use it?

Today Linux uses E820 as its' standard PC memory map representation. Now, they regret this somewhat, partially because it is less expressive than the UEFI memory map (therefore on UEFI systems they both need a converted version and the original)

But why not the UEFI memory map structure? No translation on UEFI. On non-UEFI, map the "native" format into a UEFI memory map. And if you need a type which UEFI doesn't define? Well, as said, there are 2^31 type codes reserved for arbitrary use by the OS.

Additionally, whatever part of your system sets up paging needs to make a call back into UEFI with the address map anyway. If all you have is a translated map, you're in for a world of hurt there.

Plus, the less translation you do, the easier it is to work around certain firmware bugs (e.g. on some implementations SetVirtualAddressMap incorrectly calls into boot services code. On certain MacBooks, UEFI forgets to turn off the Wi-Fi card so you can't reuse boot services data until you've enumerated the PCI bus)

[Antti]

Thank you Owen. I will think about the points you made.

[Antti]

But that ignores the fact that much of the physical address space is not "memory", is not "reserved", is not "used"... but is nothing

One thing about this. I do not think it would make the map much more bloated to have nothing described also. The main benefit is to have a map that has no gaps and all memory addresses are defined. By not having length, the memory map is forcibly well-defined and contains everything. This was the main thing I was aiming at.