Best way to implement MMU on x86_64 Higher Half kernel?

[NeonLightions]

Hi,
After a short period of time, I have learned many interesting things. Now I have 1 question: What is the best way to implement MMU when in Higher Half 64-bit kernel? I'm using stivale2 boot protocol to boot my small kernel, set up some utility things (like serial printing), set up GDT, IDT and PMM (although it still not done, but it will be finished after I sip a cup of coffee ). Now I face with Virtual Memory Management, I don't know what to do next. Can anyone suggest me?

This is my code in case you want to know what i am doing
PMM and MMU implementation is on Core/Arch/x86_64

Best Regards,

[Octocontrabass]

What is the best way to implement MMU when in Higher Half 64-bit kernel?

The MMU is hardware. You don't implement it, it's already there. Are you perhaps thinking of VMM?

Anyway, "best" is subjective, and it sounds like you have no idea what will be best for you. A good starting point is to do a bit of research into what a virtual memory manager can do, and decide which of those things you want your VMM to do. There's a very detailed explanation in the wiki here.

[Demindiro]

I agree there is no "best" scheme for implementing a VMM. Most have a trade-off one way or another.

I currently split the address range in three parts:

- A lower half for userspace.
- A quarter where the kernel itself is mapped & is otherwise free for other uses
- A quarter where all available physical memory is identity mapped (+ some pages for HPET, ACPI etc).

Identity-mapping makes it very easy to modify the page tables of all processes, which is harder with other schemes such as recursive mapping.

One obvious disadvantage is that you can only identity-map up to 1/4th of all possible physical addresses. This could be a problem with 32-bit addresses but for 64-bit it should be sufficient for a long time: right now on x64 you can identity-map up to 64 TiB of memory. If a processor supports mapping the entire 64-bit range you can identity-map up to 4 EiB(!) with this scheme.

My current (& very unfinished) heap allocator uses the identity-mapped region since it reduces pressure on the TLB. This makes it awkward to make allocations larger than 4096 bytes though. I haven't thought of a good solution for this, but I suppose you could use the free virtual address space in the other quarter if the physical memory is too fragmented for a contiguous allocation.

I also populate the upper 256 entries of the PML4 with PDP tables early in the boot process so that global mappings can easily be shared between address spaces by simply copying these entries to each PML4 table.

If you can't settle on a scheme then I'd just take one and roll with it. If it turns out to be too awkward you should still be able to replace it provided you don't let implementation details leak too much.

[rdos]

I agree there is no "best" scheme for implementing a VMM. Most have a trade-off one way or another.

I currently split the address range in three parts:

- A lower half for userspace.
- A quarter where the kernel itself is mapped & is otherwise free for other uses
- A quarter where all available physical memory is identity mapped (+ some pages for HPET, ACPI etc).

Identity-mapping makes it very easy to modify the page tables of all processes, which is harder with other schemes such as recursive mapping.

One obvious disadvantage is that you can only identity-map up to 1/4th of all possible physical addresses. This could be a problem with 32-bit addresses but for 64-bit it should be sufficient for a long time: right now on x64 you can identity-map up to 64 TiB of memory. If a processor supports mapping the entire 64-bit range you can identity-map up to 4 EiB(!) with this scheme.

I don't think identity mapping is even possible on modern 32-bit systems that typically have at least 8 GB of physical memory. For 32-bit systems, there is a trade-off between how much linear memory to assign to kernel and how much to assign to user-space. I have divided it so kernel have 1 GB and userspace has 3 GB. Large memory objects cannot be mapped in the limited kernel linear space for 32-bit, and so smarter algorithms must be invented for disc caches, but also for file caches. In my new VFS I solve this by running the file systems in server processes with 2 GB linear address space for the filesystem and 1 GB for the cache. However, I also avoid to map the caches to linear memory. The disc driver operates on physical addresses, not buffers mapped in linear memory, which is an advantage for most modern disc hardware (like AHCI). The slower IDE driver will need to map the buffer, but this is less of a problem since it is slow anyway. I only map the cache when reading meta-data in the filesystem and when giving userspace a view of a file. I think this is a good optimization both for 32-bit and 64-bit.

In 64-bit mode, much of this is not an issue, but it also makes it less of a challenge. I also feel that it is a big problem to have all physical memory mapped as if you can access something you can also corrupt it, and if you don't map all physical memory, you can only corrupt memory that actually is mapped to kernel, and not anything else.

I think the physical memory manager should be lock-free so lazy evaluation can be used. Lock-free operation cannot be achieved with linked lists, and it needs to use bitmaps or similar. When bitmaps are used, there is no need for an identity mapping of physical memory.

[Ethin]

I agree there is no "best" scheme for implementing a VMM. Most have a trade-off one way or another.

I currently split the address range in three parts:

- A lower half for userspace.
- A quarter where the kernel itself is mapped & is otherwise free for other uses
- A quarter where all available physical memory is identity mapped (+ some pages for HPET, ACPI etc).

Identity-mapping makes it very easy to modify the page tables of all processes, which is harder with other schemes such as recursive mapping.

One obvious disadvantage is that you can only identity-map up to 1/4th of all possible physical addresses. This could be a problem with 32-bit addresses but for 64-bit it should be sufficient for a long time: right now on x64 you can identity-map up to 64 TiB of memory. If a processor supports mapping the entire 64-bit range you can identity-map up to 4 EiB(!) with this scheme.

I don't think identity mapping is even possible on modern 32-bit systems that typically have at least 8 GB of physical memory. For 32-bit systems, there is a trade-off between how much linear memory to assign to kernel and how much to assign to user-space. I have divided it so kernel have 1 GB and userspace has 3 GB. Large memory objects cannot be mapped in the limited kernel linear space for 32-bit, and so smarter algorithms must be invented for disc caches, but also for file caches. In my new VFS I solve this by running the file systems in server processes with 2 GB linear address space for the filesystem and 1 GB for the cache. However, I also avoid to map the caches to linear memory. The disc driver operates on physical addresses, not buffers mapped in linear memory, which is an advantage for most modern disc hardware (like AHCI). The slower IDE driver will need to map the buffer, but this is less of a problem since it is slow anyway. I only map the cache when reading meta-data in the filesystem and when giving userspace a view of a file. I think this is a good optimization both for 32-bit and 64-bit.

In 64-bit mode, much of this is not an issue, but it also makes it less of a challenge. I also feel that it is a big problem to have all physical memory mapped as if you can access something you can also corrupt it, and if you don't map all physical memory, you can only corrupt memory that actually is mapped to kernel, and not anything else.

I think the physical memory manager should be lock-free so lazy evaluation can be used. Lock-free operation cannot be achieved with linked lists, and it needs to use bitmaps or similar. When bitmaps are used, there is no need for an identity mapping of physical memory.

I mean, that's why you use 64-bit on modern machines and you avoid 32-bit -- its no longer practical or workable without a bunch of hacks. With identity paging you don't have to map the entirety of RAM into the virtual address space; you can easily start with only your kernel mapped and then map what you need when you need it and unmap things when you don't. Its what I did in my Rust kernel and it works quite well.

[Octocontrabass]

The slower IDE driver will need to map the buffer

It doesn't need to map the buffer if you use DMA.

I mean, that's why you use 64-bit on modern machines and you avoid 32-bit -- its no longer practical or workable without a bunch of hacks.

Accessing many gigabytes of memory in 32-bit mode is never going to be practical, but I doubt you need any hacks to add one or two more address bits.

[rdos]

I mean, that's why you use 64-bit on modern machines and you avoid 32-bit -- its no longer practical or workable without a bunch of hacks. With identity paging you don't have to map the entirety of RAM into the virtual address space; you can easily start with only your kernel mapped and then map what you need when you need it and unmap things when you don't. Its what I did in my Rust kernel and it works quite well.

I pretty much disagree. Using 64-bit makes people reckless and so they map everything to kernel space (maybe even to user space if they do it wrong) just because they can. The flat memory model is in a similar vain: You sacrifice the superior protection of segmentation and let everything be accessible.

Also, if you map physical memory it will be in the virtual address space. If it wasn't, why would you map it? All it takes is a malformed pointer and you can write to some other process or steal information that should be protected within the address space of the process. Any way you look at this, mapping all of physical memory makes it possible to access all virtual address spaces regardless if you are executing code in them or not. This basically takes away all the protection of paging.

Besides, I wouldn't call the algorithms used for file caches and disc device drivers for hacks. They are smart algorithms that avoid exposing file system data to the accessible virtual address space and that additionally work better since typical drivers need physical addresses and not virtual.

[rdos]

The slower IDE driver will need to map the buffer

It doesn't need to map the buffer if you use DMA.

I mean, that's why you use 64-bit on modern machines and you avoid 32-bit -- its no longer practical or workable without a bunch of hacks.

Accessing many gigabytes of memory in 32-bit mode is never going to be practical, but I doubt you need any hacks to add one or two more address bits.

Well, you cannot map a complete 64 GB file in long mode either if you only have 16 GB of physical memory. So, there is always a need to be able to handle the case were you cannot map a complete object to linear memory. The only difference between 64-bit and 32-bit is when you need to do this. You might argue that you can demand-page it, but then if you use random access this will become very inefficient. The code must be written so it tries to optimize locality of access, and this is the major factor in performance, not how large chunks you can map at the same time.

That'w why my analysis program that runs in 32-bit mode and use 60 GB of data would not be faster in long mode. In fact, I only map 2MB at a time, and since the code has high locality, the change of mapping has no impact on performance.

[Octocontrabass]

That'w why my analysis program that runs in 32-bit mode and use 60 GB of data would not be faster in long mode.

An "analysis program" sounds like exactly the sort of thing that would be faster in 64-bit mode, just because it wouldn't be limited to 8 SIMD registers. (Of course this depends on your choice of algorithms and compiler optimizations.)

In fact, I only map 2MB at a time,

High-end CPUs have caches that are bigger than that. You might be preventing the CPU from effectively prefetching data.

[rdos]

That'w why my analysis program that runs in 32-bit mode and use 60 GB of data would not be faster in long mode.

An "analysis program" sounds like exactly the sort of thing that would be faster in 64-bit mode, just because it wouldn't be limited to 8 SIMD registers. (Of course this depends on your choice of algorithms and compiler optimizations.)

The inner loop consist of multiplying a sin() function (using an 18-bit table) with an array of 14-bit integers. This is typically done on hundreds of values per operation. The code uses assembly as I don't trust the compiler would be able to provide better optimizations than my hand-coded assembly code.

[Octocontrabass]

The code uses assembly as I don't trust the compiler would be able to provide better optimizations than my hand-coded assembly code.

You might be surprised. GCC and Clang have gotten very good. The only requirement is that you write your code in a way that allows the optimizations; for example, in C you may need to use the "restrict" keyword. There are also builtins you can use to tell the compiler about alignment and loop count restrictions to further improve the generated code.

[Ethin]

That'w why my analysis program that runs in 32-bit mode and use 60 GB of data would not be faster in long mode.

An "analysis program" sounds like exactly the sort of thing that would be faster in 64-bit mode, just because it wouldn't be limited to 8 SIMD registers. (Of course this depends on your choice of algorithms and compiler optimizations.)

The inner loop consist of multiplying a sin() function (using an 18-bit table) with an array of 14-bit integers. This is typically done on hundreds of values per operation. The code uses assembly as I don't trust the compiler would be able to provide better optimizations than my hand-coded assembly code.

Trust me when I say that you can't write better assembly than the compiler. The compiler knows far more about your program than you do. It after all can hold your entire program in memory and analyze it in its entirety. Good luck doing that in your mind on a program that's 15000 LoC. When it comes to "who can write better assembly", the compiler always wins. Its an extremely rare moment when you can outsmart a compiler these days. And I'm not talking about intrinsics, just normal code.

[Ethin]

I mean, that's why you use 64-bit on modern machines and you avoid 32-bit -- its no longer practical or workable without a bunch of hacks. With identity paging you don't have to map the entirety of RAM into the virtual address space; you can easily start with only your kernel mapped and then map what you need when you need it and unmap things when you don't. Its what I did in my Rust kernel and it works quite well.

I pretty much disagree. Using 64-bit makes people reckless and so they map everything to kernel space (maybe even to user space if they do it wrong) just because they can. The flat memory model is in a similar vain: You sacrifice the superior protection of segmentation and let everything be accessible.

Also, if you map physical memory it will be in the virtual address space. If it wasn't, why would you map it? All it takes is a malformed pointer and you can write to some other process or steal information that should be protected within the address space of the process. Any way you look at this, mapping all of physical memory makes it possible to access all virtual address spaces regardless if you are executing code in them or not. This basically takes away all the protection of paging.

Besides, I wouldn't call the algorithms used for file caches and disc device drivers for hacks. They are smart algorithms that avoid exposing file system data to the accessible virtual address space and that additionally work better since typical drivers need physical addresses and not virtual.

Its interesting that you still maintain that segmentation is superior. Clearly it isn't or we'd still be using it today.
First: paging in no way requires that a developer be reckless. Implemented correctly, paging can provide the same security features that segmentation provided, minus all its disadvantages. If when implementing paging you choose to be reckless, that's not the fault of 64-bit paging, that's your fault. Blaming the computer for your own stupidity is... Well, stupidity at its finest.
Second: mapping all of physical memory into a virtual address space doesn't mean that processes can access that physical memory. If you have a process in another address space and you don't map all of physical memory in that processes address space, the only way that process is going to be able to access your physical memory mappings is by taking advantage of software/hardware vulnerabilities like meltdown/spectre, and if a process is doing that segmentation isn't going to protect you either -- the whole point of meltdown in particular is to melt those barriers that separate processes, regardless of what method (segmentation or paging) your using. If that happens, your screwed anyway.
Third: paging doesn't allow processes to access one anothers memory without it being mapped first. That's literally the whole point: to make a process think that its the only thing that the computer is doing. If process 1 and 2 are in separate virtual address spaces, they can only access the addresses mapped in those address spaces. If I don't map any of process 2's memory into process 1's address space, process 1 can't access process 2's memory at all -- that'll either cause a page fault or process 1 will read its own memory. If process 1 and 2 are kernel-mode processes (and therefore can change the page tables at will), then the risk is higher -- either process can screw around and break things or read arbitrary memory, but that risk occurs with segmentation too: if a process can muck about with the segment registers, your screwed. Paging also has the advantage of being able to share memory without having to duplicate it. If I want to send data to process 2 from process 1, all I have to do is map the page containing the data I'd like to share into process 2's address space. The underlying physical address doesn't need to change, and I don't have to copy anything around. If I want both processes to be able to access the same memory, all I have to do is map it twice. Again, the underlying address in memory doesn't have to change. Or I could map the memory into process 2's address space and unmap it in process 1's. You can't do that with segmentation.
Of course, the other problem with segmentation is swapping to disk -- you can't swap part of a segment to disk and swap it back, you have to swap the entire segment to disk and reload it (which can cause memory fragmentation). With paging I can swap single pages to disk and back and don't have to do something ridiculous like, I dunno, swapping the entire virtual address space to disk and back. Like I said: if segmentation were truly superior to paging, we'd still be using it. Clearly, smarter heads believed that paging was a better and more secure option than segmentation. Paging certainly isn't perfect -- processor vulnerabilities can break its security guarantees -- but the same holds for segmentation, and I'm pretty sure that an OS solely using segmentation isn't immune to spectre or meltdown.

[nullplan]

Its interesting that you still maintain that segmentation is superior. Clearly it isn't or we'd still be using it today.

That's a fallacy. Just because something is more popular doesn't mean it is superior. Only that it is more dominant. We use x86 and not, say, PowerPC, because all the compiled programs are written for it, and making them architecture-agnostic is work nobody wants to spend. Even Intel failed to kill the architecture, and not for lack of trying.

And in this specific case, we don't use segmentation because it doesn't integrate well into any language higher level than assembler. And because the flat address space has pretty much become universal. From the bathroom scale to the space shuttle, everything is using flat address spaces.

First: paging in no way requires that a developer be reckless.

Reading comprehension! He didn't write that. I do disagree with rdos here, but try to attack his actual points, not the strawman version. For example:

Second: mapping all of physical memory into a virtual address space doesn't mean that processes can access that physical memory.

He didn't write that either. He wrote that having lots of address space available makes people recklessly map all of physical memory into kernel space.

And it is a fair point that an error in the kernel can corrupt more if more physical memory is mapped. Absolutely. An error in the USB driver would ordinarily only affect USB performance, but with all of physical memory mapped, you could end up writing USB disk contents into the page tables of some process, thereby breaking it. My counterpoint to that is that an error in the kernel is pretty much always catastrophic (so kernel errors must be fixed promptly), and the benefits of always having all of physical memory mapped (trivial mapping from physical to virtual address; not so many TLB shootdowns, which are always a barrel of fun, especially these days with hundreds of cores being a possibility; less TLB pressure due to lack of temporary mapping) are too big to forego, but that is a judgment call.

[Ethin]

Its interesting that you still maintain that segmentation is superior. Clearly it isn't or we'd still be using it today.

That's a fallacy. Just because something is more popular doesn't mean it is superior. Only that it is more dominant. We use x86 and not, say, PowerPC, because all the compiled programs are written for it, and making them architecture-agnostic is work nobody wants to spend. Even Intel failed to kill the architecture, and not for lack of trying.

And in this specific case, we don't use segmentation because it doesn't integrate well into any language higher level than assembler. And because the flat address space has pretty much become universal. From the bathroom scale to the space shuttle, everything is using flat address spaces.

Right, but if segmentation was truly the superior option, the C standard could've been changed back when people were trying to decide what would be dominant. Back then, such things were still changeable because neither had really fully taken hold -- people were always trying out new models and concepts of virtual memory. But paging won the battle, so to speak, and the languages followed. Is it unreasonable, then, to suggest that if segmentation was truly the superior option, paging wouldn't have dominated?