How do *you* page?

[AndrewAPrice]

I'm curious on how people implement paging and memory management in their OS.

I have a functional paging system implemented. In my OS, the kernel has a page table which maps 0->4MB physical to 0->4MB virtual. Each process has list a pages (which can be anywhere >4MB), and also its own page table which maps these pages into 4->8MB virtual memory. When the kernel boots, a page directory gets created in memory. The first entry of the page directory (0->4MB) is the kernel's page table. The second entry of the page directory (4->8MB) is the current process's page table. To switch into another process's memory space, I simply swap the second page directory entry to point to the process's page table.

This system has limitations. The kernel always has 4MB of memory, and processes can't have any more than 4MB either.

I'm asking people how they implement paging and handle memory in their OS because I'm trying to find answers to a few problems/questions;
- What area of virtual memory should be reserved for the kernel?
- Where should user programs be loaded (at 4MB in mine, but leaving 4MB just for the kernel isn't very much).
- Do you give each process their own page directory? Or do you construct them in memory on each context switch?
- How do you store which pages are associated with the process? (I use a linked list of pages, when a page is 'attached' to or 'removed' from a process, I regenerate the page table)
- How do you store which pages are associated with the kernel? (I do a direct 1:1 with the first 4MB of memory.)

[Brendan]

Hi,

I'm asking people how they implement paging and handle memory in their OS because I'm trying to find answers to a few problems/questions;
- What area of virtual memory should be reserved for the kernel?

For plain paging kernel space is from 0xE0000000 to 0xFFFFFFFF (but this may change in future versions). For PAE kernel space is from 0xC0000000 to 0xFFFFFFFF. For long mode kernel space is the upper half of the linear address space, but I only actually use part of it.

- Where should user programs be loaded (at 4MB in mine, but leaving 4MB just for the kernel isn't very much).

I used to load all processes at 0x00001000, however this will change. For the next version of my OS processes will be loaded at an address determined by the executable's header (although I expect almost all processes will still end up starting at 0x00001000).

- Do you give each process their own page directory? Or do you construct them in memory on each context switch?

I actually give each thread it's own page directory (or page directory pointer table, or PML4), although this isn't very normal (it's part of my OS design that doesn't make sense for other OS designs).

- How do you store which pages are associated with the process? (I use a linked list of pages, when a page is 'attached' to or 'removed' from a process, I regenerate the page table)

Mostly, I just store the information in the page tables, page directories, etc, and I only use additional data structures when necessary (e.g. memory mapped files, although I've haven't implemented that yet).

- How do you store which pages are associated with the kernel? (I do a direct 1:1 with the first 4MB of memory.)

I use the information in the page tables, page directories, etc for tracking which pages are associated with the kernel. I don't do a 1:1 mapping of any normal RAM pages - I dynamically select the best pages to use (according to page colouring, NUMA domain and other factors). This is slightly more complicated, as for NUMA systems I have a seperate copy of the kernel's code and some of the kernel's data for each NUMA domain to reduce "slow" memory accesses (where a CPU needs to access RAM that isn't "close").


Cheers,

Brendan

[jerryleecooper]

For now my OS only support 16mb, so all my processes has identity mapped 16mb for the kernel, but Im a bit confused with that. When there's an exception, is the cr3 field of the tss replace the cr3 register?
I load my executables at 0xc0000000 because they are binary and it's what their -text is at, the user stack is at 0xb0000000. That is only true for user processes that are c0x, normal user processes and kernel processes shares kernel memory, they don't have their own weird memory space. When a c0x process want the 0xa00000 pointer for vga memory, I map it at 0x8000000. So you can see right now that the memory map of the c0x processes is fragmented and not very well tought.
When a c0x process want some memory I map it somewhere, the memory comes from smallbank, which is the heap from 16mb to 1mb+kernelsize. memory at 640kb to 0x7c00 is minibank.

[Combuster]

My system is exokernel-based, so for most part managing paging structures is up to the user.

The net result is that the paging structures might not be present in the current address space. The kernel's part of the address space and the corresponding pagetables are known however and the kernel reserves some space therein to map the needed paging structures in order to modify them. userland applications can also decide to map those structures at a selected position so they can be accessed faster.

The kernel itself does not occupy much space. It is loaded at 2MB and is identity mapped to allow for paging to be disabled and re-enabled at will. This leaves everything under the 2MB mark free for running V8086 tasks, and everything above 3MB for general purposes. (in PAE modes, this allows a 2MB page to cover the entire lower memory without security concerns.)

Applications are linked with relocation info. The program loader can therefore choose the optimal location at runtime (to keep clear of areas where shared libraries / DLLs have been loaded and to optimize for tlb coverage etc).

Each full address space has its own page directory. However address spaces can be shared using segmentation methods, allowing for several programs to share one pagetable. Applications can also choose to run on just segmentation (paging disabled), where it will be associated a LDT instead. Exokernel principles dictate that the fragmentation issues thereof will obviously be delegated to userland. Pages belonging to the kernel will simply be marked with an appropriate setting of the U/S bit.
At least, that's the design.

[AndrewAPrice]

I'm going to redesign my memory layout.

I've decided that the best route to go is to load the kernel at 3GB, and load all processes at 4MB+4KB. I'll map the first 4MB to page tables. This will give me a layout like:

Code: Select all

0x0000000: First page table
0x0001000: Second page table
0x0002000: Third page table
0x0003000: Fourth page table
               ... etc
                 Space from 0->4MB will be reserved for the loaded page tables.
0x0400000: Page directory (4MB)
0x0401000: Start of process memory (4MB+4KB)

               ... Reserved for process memory. This leaves 3067MB/3,141,628KB for the program.

0xC0000000: Start of kernel.

               ... Reserved for kernel memory. Highly unlikely it'll use 1GB.

0xFFFFFFFF: End of memory

The advantage of having the kernel so high (at the top of the memory) means I can change this value later without having to recompile each user program since they will always load at 0x00401000.

How do I go about setting up a higher half kernel? I use GRUB to load my kernel which loads my kernel at 0x00100000. How do I reallocate it to the top? I think I could map it to 0xC0100000, jump to the [code+3GB], then unmap the lower memory. I'd have to use assembly before I enable paging so that every address is referred to as [address-0xC0000000], but link my kernel to 0xC0100000. But then, wouldn't GRUB try to load this at 3GB physical memory?

Secondly, when I do things, like set up my IDT, do I need to load their physical or virtual address? Also, will this interfere with DMA? (I'll reserve the first 64KB of physical memory for it, and map 0->64KB to 3GB->3GB+64KB.)

What other things should I know about when using a higher half kernel?

[AndrewAPrice]

Hmm.. would it be easier for GRUB if I used a lower-half kernel? Then GRUB can load it at 1MB like always, and I'll place my user programs at 1GB. I don't like this idea at all, since I want to be able to move the kernel around without effecting the position user-programs should load at.

[pcmattman]

Hmm.. would it be easier for GRUB if I used a lower-half kernel? Then GRUB can load it at 1MB like always, and I'll place my user programs at 1GB. I don't like this idea at all, since I want to be able to move the kernel around without effecting the position user-programs should load at.

My kernel is at the 1 MB mark (lower-half), and userland programs start at 0x400000 (4 MB mark).

It works nicely, imho. My kernel is at worst 100 kb big so I don't have to worry about it not fitting.

[Brendan]

Hi,

Hmm.. would it be easier for GRUB if I used a lower-half kernel? Then GRUB can load it at 1MB like always, and I'll place my user programs at 1GB. I don't like this idea at all, since I want to be able to move the kernel around without effecting the position user-programs should load at.

The easiest way would be to accept the physical memory layout that the boot loader felt like using, regardless of whether it's "good" or not.

IMHO it depends why your writing an OS and how it's designed. For example, if your OS is for your own fun or education purposes only then development time might be more important than trying to write the "best" OS you can; or if the OS uses a single address space and most of your code is some sort of byte-code that's JIT compiled when it's run then it might be easy to change things at any time; or if your OS is a prototype that you plan on rewriting later it might not matter what you do.

My OS supports several different boot loaders and can't rely on how one of them felt like doing things. During boot my code detects some things and then decides if it should start a 32-bit kernel with plain paging, a 32-bit kernel with PAE or a 64-bit/long mode kernel. Then (for all kernels) it dynamically allocates physical pages while setting up paging (before any kernel code is run) to make sure it's using the "best" physical pages it can. For me it's better to give processes the lower part of the linear address space (e.g. from 0x00000000 to a kernel-dependant "top of usable address space") , and I can't assume that the page table area will be 4 MB (with PAE the page table area might be 8 MB and in long mode the page table area might be several GB).

I also wish that the GRUB/Multiboot documentation was more precise. GRUB loads one file that is executed by GRUB and also (optionally) loads more files. Except for some badly worded documentation, there's no reason that one (or more) of the modules can't be the kernel/s, and no reason that one or more of the modules can't be larger files (e.g. boot image/s) that contain one or more kernels. The file that is executed by GRUB can be just some disposable code that sets things up for a kernel; or it could be the first of many pieces of code that does part of the work before any kernel is started.

@pcmattman: For one of my previous OSs there were 6 different kernels that were all between 50 KB and 64 KB. The boot code (which included code for auto-detection, decompression, a boot menu and kernel setup code; which was all discarded during boot to save memory) consisted of several seperate pieces of code that adds up to about 120 KB not including the boot loader itself (i.e. the kernels were all smaller than the setup code). The kernels were micro-kernels and needed up to 1 GB of kernel space to ensure that there was enough space to run the maximum number of processes and threads that the kernels supported, for message queues and for other data structures the kernels used (memory management, tables for I/O port protection and IRQ handling, tables describing CPUs and the relationships between CPUs and NUMA domains, etc).

If each thread costs 4 KB of kernel space, then with 4 MB of kernel space the OS can't even handle 1024 threads (even if the computer has 32 GB of RAM and 32 CPUs).


Cheers,

Brendan

[AndrewAPrice]

Thanks Brendan. I'm going to load my processes at 0, giving them the entire 3GB, and place the page tables somewhere in kernel memory (I'm thinking about the last 4MB).

Anyway, I still have a few unanswered questions from above:

How do I go about setting up a higher half kernel? I use GRUB to load my kernel which loads my kernel at 0x00100000. How do I reallocate it to the top? I think I could map it to 0xC0100000, jump to the [code+3GB], then unmap the lower memory. I'd have to use assembly before I enable paging so that every address is referred to as [address-0xC0000000], but link my kernel to 0xC0100000. But then, wouldn't GRUB try to load this at 3GB physical memory? Confused

Secondly, when I do things, like set up my IDT, do I need to load their physical or virtual address? Also, will this interfere with DMA? (I'll reserve the first 64KB of physical memory for it, and map 0->64KB to 3GB->3GB+64KB.)

What other things should I know about when using a higher half kernel?

EDIT: I've got my kernel loading at 3GB. I'm having to re-write most of my memory manager. My new memory manager isn't going to depend on any 'static' variables other than knowing where the kernel was loaded (3GB). GRUB will provide other how big my kernel is, so my manager will start utilizing memory directly after the kernel, so hopefully minimal memory will be wasted.