Paging design, Lower half kernel, potential problems?

[davem]

Are there any issues with just identity mapping the kernel and sticking it in all ring 3 address spaces as read only? Why would we want to make it higher half? Also, why do people either a) map the page directory into itself or b) store the physical addresses when they could just walk the page tables?

[thooot]

Identity mapping the kernel is fine I suppose, but I don't think there's much point in having it visible in ring 3. The reason to use ring 0 is so you can use system instructions that aren't available in ring 3. If the kernel is visible in ring 3 then that means its not marked as system memory and you can't use the system instructions (or its mapped in two areas, one spot marked as system and the other not). The higher half thing is just a convention. You can put it at any random area you want and have user memory and kernel memory all interspersed if you want, its just more complicated.

For the page tables you need to have them mapped somewhere in order to access them. You can't walk the page table unless the page table is mapped somewhere in the virtual address space. If your physical pages are identity mapped then you can use that to walk the tables, but not all kernels do this. The mapping the page directory to itself is just a nice to trick that lets you automatically access any valid page in the system without having to do any additional mapping logic.

[Brendan]

Hi,

IMHO identity mapping or direct mapping the kernel (and/or identity mapping or direct mapping a fixed area of the physical address space) isn't as flexible and causes problems later on when you want to implement more advanced features. For example, my OS is designed to be resistant to faulty RAM, and is designed to do certain NUMA optimizations, where both of these things are impossible or ineffective if you assume the kernel is loaded at a fixed physical address and then identity mapped or direct mapped. At the beginning of an OS project it's hard to guess which features you might want to implement in future, so flexibility is a "good thing(tm)", which makes identity mapping or direct mapping the kernel a bad thing (IMHO).

Identity mapping the kernel is fine I suppose, but I don't think there's much point in having it visible in ring 3. The reason to use ring 0 is so you can use system instructions that aren't available in ring 3. If the kernel is visible in ring 3 then that means its not marked as system memory and you can't use the system instructions (or its mapped in two areas, one spot marked as system and the other not).

No. If the kernel is visible in ring 3, then the only difference it makes is that the kernel is visible in ring 3 (the kernel can still do everything else exactly the same, including using all system instructions).

The problem with having the kernel (and/or the kernel's data) visible in ring 3 is that the kernel (and/or the kernel's data) is visible in ring 3. Basically it violates the "Principle of least privilege". For a simple example, something like "Address space layout randomization" may become worthless if you can find out where the process has it's libraries, stack, heap, etc by reading from the kernel's data structures.

higher half thing is just a convention. You can put it at any random area you want and have user memory and kernel memory all interspersed if you want, its just more complicated.

The way I see it, is that all programmers prefer to have their code start at zero (or close to zero), because it makes it easier for debugging (e.g. the address 0x00001234 is easier for programmers than 0x45671234) and because it might make it easier for the CPU (e.g. using words or dwords for addresses, instead of dwords or qwords).

Only a few programmers write the kernel, but (hopefully) hundreds of programmers will write applications, etc. It's better to make things easier for hundreds of programmers than to make things easier for a few programmers, so applications/processes have their code start at zero or close to zero (and therefore the kernel can't have it's code start at zero or close to zero, at least not without causing more hassles than it's worth).


Cheers,

Brendan

[mangaluve]

Im about to implements paging/memory managment in my own kernel and I've always thought that identity mapping of the kernel was the way to go. What are the alternatives? Since I use C for my kernel, it has to be in linear memory right? And I tell the linker about it's fixed physical location. Doesn't the "code" needs to know where in memory it is (virtual or not)?

[Brendan]

Hi,

Im about to implements paging/memory managment in my own kernel and I've always thought that identity mapping of the kernel was the way to go. What are the alternatives?

The alternative is to have some setup code that initializes paging before the kernel itself is started. In this case it doesn't make any difference where the kernel is in physical memory, you don't need to do strange hacks (e.g. rely on segment wrap-around) during boot, and all of the kernel's code can be linked for a fixed virtual address.

As an added bonus, it means that this setup code is easy to dispose of later (it doesn't end up in the kernel wasting RAM after boot).

Since I use C for my kernel, it has to be in linear memory right? And I tell the linker about it's fixed physical location. Doesn't the "code" needs to know where in memory it is (virtual or not)?

The compiler/linker needs to know what address the code will be running at - otherwise simple things like function pointers won't work. Eventually the kernel will be in virtual memory, therefore you need to tell the linker about it's fixed *virtual* address (which creates a problem during boot if the kernel isn't running at that address). For example, maybe you design your OS so that the kernel runs at the virtual address 0xC0000000, but during boot it can't run at the physical address 0xC0000000 because there's no RAM there, and therefore during boot it's not running at the address it was compiled/linked for.

You could use segmentation to get around this. For example, create segments with "base = 0x40100000". In this case "base + offset = 0x40100000 + 0xC0000000 = 0x100100000 = physical address 0x000100000" because it's truncated to 32-bits. The problem here is that it's a pain in the neck for other addresses. For example, video display memory might be at 0x000B8000, but with freaky segmentation you get "0x400100000 + 0x000B8000 = 0x4001B8000" and you'd need to use the offset 0xBFFB8000 to access video display memory to account for segmentation.

Of course relying on segment wrap-around won't work for 64-bit kernels. In this case doing things properly (having setup code that initializes paging before the kernel itself is started) is the only sane alternative.

Now, before someone says "but Linux does this so it must be good", let me point out that Linux was originally written by as a hobby kernel for 80386 (and wasn't originally intended to be a successful kernel, and wasn't designed to handle modern hardware that didn't exist at the time, and didn't support any advanced features, and in some cases still doesn't). Identity mapping probably saved Linus 50 hours of work initially, and probably costed volunteers thousands of hours of work later on, and now there's so much code that relies on this identity mapping that it'd be incredibly difficult to remove. With hindsight, you can do better...


Cheers,

Brendan

[clange]

The way I see it, is that all programmers prefer to have their code start at zero (or close to zero), because it makes it easier for debugging (e.g. the address 0x00001234 is easier for programmers than 0x45671234) and because it might make it easier for the CPU (e.g. using words or dwords for addresses, instead of dwords or qwords).

This is the absolutely best argument I have heard for using a higher half kernel. I had planned to just reserve the first 64 mb of the address space for the kernel (it being simple and me being lazy). But know I see no way around using a higher half kernel. The design benefits far outweigh the implementation cost as you also point out in your later post.

Your insight into OS development and your posts really helps me design a better OS.

So thanks

clange

[mangaluve]

Why is it a problem if both applications and the kernel starts at zero (in the virtual memory)?

[Brendan]

Hi,

Why is it a problem if both applications and the kernel starts at zero (in the virtual memory)?

Because you can't have 2 pieces of code in the same pages (one overwrites the other).

You could use segmentation (e.g. have the kernel's CS, DS, ES and SS with "base = 0xC0000000") but then you'd need to convert pointers between "user segmentation" and "kernel segmentation" (e.g. adding or subtracting 0xC0000000 from them) whenever pointers are passed between user space and the kernel (and for other things - e.g. CR2 in the page fault handler). This makes it more annoying than just linking the kernel to run at 0xC000000.

Also, in some cases for some OSs, data segment registers don't need to be changed when the CPU goes from CPL=3 to CPL=0 (or changed again when the CPU goes from CPL=0 to CPL=3). Basically it's possible to use the same DS/ES/FS/GS segment registers for CPL=3 code and CPL=0 code; which reduces kernel API overhead and IRQ handling overhead, because reloading a segment register is slow (due to protection checks, etc).

Lastly, SYSENTER and SYSCALL assume that segment base addresses are zero, so you can't use segment registers if you want to support these instructions.

The only other alternative is to have the kernel in it's own separate virtual address space (rather than having the kernel in part of all virtual address spaces). This idea sucks the most (lots more overhead and lots more complex, with no sane advantage).


Cheers,

Brendan

[mangaluve]

Okey thanks! I've always thought that it would keep things simple to have the kernel running in it's own address space. So what I should do is that the kernel is always mapped in every address space? Where should I put my kernel (virtual address)? Should it be placed in the highest part of the memory (perhaps I want to use a really large application, then I cant have the kernel in the middle of the virtual memory). Where is the kernel put in Linux for instance?

[Colonel Kernel]

The only other alternative is to have the kernel in it's own separate virtual address space (rather than having the kernel in part of all virtual address spaces). This idea sucks the most (lots more overhead and lots more complex, with no sane advantage).

Mac OS X does this (not sure if this is changing in Snow Leopard, but up to Leopard it works this way). I think it was a carry-over from porting to Intel from PPC. AFAIK kernels on PPC usually run with paging disabled.

There are two sane advantages, although they are probably outweighed by the disadvantages:

• You can have a really big kernel address space (e.g. -- for a whopping big disk cache).
• It allowed Apple to keep the kernel 32-bit while still being able to support 64-bit processes. This meant they didn't have to get everyone to port their drivers to 64-bit right away (this is happening now in preparation for Snow Leopard, which will be the first 64-bit OS X kernel). This is only an advantage if your OS already has a lot of 32-bit drivers, which I doubt applies to many hobby OSes.

[mangaluve]

But what is the reason that you'd want the kernel mapped in the address space of an application? The application can't access the kernel code anyway..

[Colonel Kernel]

When an interrupt occurs or the app invokes a system call, the CPU switches to ring 0. There has to be at least something mapped into the app's address space to handle such events. The reason to put the rest of the kernel there too is to avoid switching to another address space to handle every interrupt, exception, or system call. Switching address spaces on x86 (i.e. -- reloading CR3) flushes the TLB, causing TLB misses, which really slow things down.

Plus, any system call that involves copying data will be slower if it has to cross address space boundaries. For example, if the kernel is mapped into the app's address space and the app wants to write a large buffer to some I/O device, the kernel can just copy the data directly from the app's buffer (after some sanity checking). If the kernel were in a different address space, it would have to map the app's buffer into its own address space first before copying, which again will result in TLB invalidations and other overhead.

[mangaluve]

Makes sense, thank you!
But when I enable paging, the code that enables it must be identity-mapped, right? (otherwise we cannot gurantee what the next instruction will be?). Do I have to write a "loader" that loads the real kernel into memory and sets up paging (with this small loader identity mapped) and then jump to the real kernel? So my bootloader loads this loader. It loads the kernel to some location, sets up the page directory and the page tables needed for the kernel, enables paging, and then jump to the kernel?

[Colonel Kernel]

Makes sense, thank you!
But when I enable paging, the code that enables it must be identity-mapped, right? (otherwise we cannot gurantee what the next instruction will be?). Do I have to write a "loader" that loads the real kernel into memory and sets up paging (with this small loader identity mapped) and then jump to the real kernel? So my bootloader loads this loader. It loads the kernel to some location, sets up the page directory and the page tables needed for the kernel, enables paging, and then jump to the kernel?

That's probably the cleanest way of doing it. It is also possible to have the kernel map itself to the higher-half with a bit of position-independent code, like in the Higher Half Bare Bones tutorial. If you have the patience though, I'd recommend having your own loader set up your kernel in the higher half.

[mangaluve]

Thanks! So, just to make sure I got all the reasons, this is the deal:
I want the kernel mapped in the address space of a user application (for instance for interrupts). And I want the application in the lower part of the memory (for debugging purposes for instance) so the kernel has to be in the high part. Now I cannot identity-map the kernel, since I don't know at compile-time how much memory i will have (but without identity mapping I could put the kernel at a really high virtual address, regardless of how much RAM I've got. This would allow user applications to be really large, without the kernel code interfering). And if I don't want to identity map, I should have a special loader that loads the real kernel and enables paging. Is this correct?