OSDev.org

A small introduction to my background: I've started programming in assembly maybe 2 years ago, then reverse engineering a little bit. I coded a small (not completed) kernel in assembly. Now last year I've been busy learning C. I'm now doing my (new) kernel in C and I'm busy with MM now.

I think I'm going to use a stack for free pages, and use GRUB's Multiboot information structure to know how many physical memory is installed.

1. Where should I store the kernel's page directory? Personally, I thought linear address 0x200000 would be a fine place.
2. What should happen when I call kallocpage()? I thought: pop an address off the stack and map it in the correct page table.
3. What should happen when I call kfreepage()? I thought: push the address back onto the stack and unmap the corresponding page table entry, then invalidate the TLB entry using the "INVLPG" instruction.

Any extra ideas? Or maybe you have/want to correct some of my thoughts.

All welcome...

-- BugHunter

1. I can tell you the first misconception is deciding where to place the Page Directory and Page Table.

2. & 3.
You will find it easier to build two seperate systems and label them in general as Physical Memory Manager and Virtual Memory Management.

Physical Memory Manager
uintptr_t pmm_Alloc(uintptr_t count);
void pmm_Free(uintptr_t page, uintptr_t count);
Virtual Memory Management
typedef uint32_t VMMDIR;
VMMDIR vmm_CreateDirectory();
uintptr_t vmm_Alloc(VMMDIR dir, uintptr_t count);
uintptr_t vmm_AllocEx(VMMDIR dir, uintptr_t page, uintptr_t count);
void vmm_Map(VMMDIR dir, uintptr_t phy, uintptr_t virt, uintptr_t count);
void vmm_Free(VMMDIR dir, uintptr_t page, uintptr_t count);

Where *_Alloc provides you with the ability to specify one or multiple contiguous pages to be allocated from anywhere, while *_AllocEx allows one or multiple contiguous pages to be allocated at page.

How you decide to store the free and used pages in the Physical Memory Manager: stack(s), tree(s), or bitmap(s) is completely up to you.

The major point is to first get the pmm up and running, then make a call to create your Page Directory with vmm_CreateDirectory which makes a call to the pmm_* set of functions and dynamically allocates a page directory.

The entire setup should be flexible and if you notice the vmm_* set of function take a extra argument in contrast to the pmm_* set of functions which is the VMMDIR dir argument. Since I am sure you will want to take advantage (or be able to take advantage) of managing multiple Address Spaces through the usage of multiple Page Directories and Page Tables.

VMMDIR g_k_vdir;
g_k_vdir = vmm_CreateDirectory();
vmm_Map(g_k_vdir, KERNEL_PHYSICAL_LOAD_ADDRESS, KERNELL_PHYSICAL_LOAD_ADDRESS, KERNEL_SIZE/4096);
vmm_Map(g_k_vdir, 0xb8000, 0xb8000, 1); // vga for debugging
vmm_Map(g_k_vdir, g_k_gdt, g_k_gdt, g_k_gdt_length/4096);
vmm_Map(g_k_vdir, g_k_idt, g_k_idt, g_k_idt_length/4096);
vmm_Map(g_k_vdir, g_k_stack, g_k_stack, g_k_stack_length/4096);
vmm_On(g_k_vdir);

2. What should happen when I call kallocpage()? I thought: pop an address off the stack and map it in the correct page table. Yes
3. What should happen when I call kfreepage()? I thought: push the address back onto the stack and unmap the corresponding page table entry, then invalidate the TLB entry using the "INVLPG" instruction. Yes

Why? Don't I need to store it somewhere? I should find a place first to store the kernel's PD, no?



Could you explain this part in more detail? I mean the part about dynamically allocating a page directory. How does it happen?

As a side note, I have no support for processes in my kernel yet.

EDIT: Another question, I should have ONE big stack of free pages, right? And that stack should be part of the kernel's memory, which is mapped in each process (later on when my kernel supports processes).

One of the ways to implement a physical memory stack is to just have a large array of addresses to all free pages, and a top of stack pointer. However, there is a much neater and more interesting way that only actually uses up 4 bytes of space (for 32-bit). Namely:

- have a pointer to the first free page, stored in kernel space for all processes
- have the first dword of the first free page point to the second free page
- have the first dword of the second free page point to the third free page
and so on.

Then, when you want to allocate a page, you take the address of the first free page from your pointer in kernel space and map it to where you want it. You then read the first dword which points to the next free page and write that value to your kernel pointer. Then clear the page with zeros.

Freeing a page is basically accomplished by inserting it at the start of the list, i.e. write the kernel pointer to the page to free then point the kernel pointer to the freed page.


Well, you get a free physical page from the physical memory allocation function, so then just use that as the page table/directory. It means you don't need it to be at a particular address. The only requirement for pare tables/page directories is that they are 4kB-aligned, so as long as your pmm_alloc function returns 4kB-aligned pages, you should be okay.

Regards,
John.

Physical Memory Manager
uintptr_t pmm_Alloc(uintptr_t count);
void pmm_Free(uintptr_t page, uintptr_t count);
Virtual Memory Manager
typedef uint32_t VMMDIR;
VMMDIR vmm_CreateDirectory();
uintptr_t vmm_Alloc(uintptr_t count);
uintptr_t vmm_AllocEx(uintptr_t page, uintptr_t count);
void [i]vmm_Free(uintptr_t page, uintptr_t count);

First,
/// process GRUB's memory map and add free pages into the pmm using pmm_Free(page, count), or derive a special function to add pages on boot.
... code doing this ...

Now, you should have the ability to call the pmm_Alloc function and get free pages when you need them for usage around the system.
/// create a page directory for the kernel using pmm_Alloc(count=1), OR use the function vmm_CreateDirectory().
... code doing this ...

How to build a physical memory manager that dynamically allocates it's own memory stack space?



Now the virtual memory management functions can dynamically allocate the memory they need, right?

But what about security and protection then? This DWORD at the start of each page could be overwritten easily.



Indeed, it's neater to use the PMM to allocate memory for a PD.


Why then build a function called vmm_CreateDirectory() if pmm_Alloc() can do the same? Or am I missing some part (probably I am)?



I like your idea of being able to use pmm_Free() to initialize the stack if there is no stack yet. I'm going to give these things a thought

Not once you enable paging.

Regards,
John.

Hi,



The PD needs to be stored somewhere, but do you care exactly where? In general it doesn't matter what physical address is used and it can be allocated dynamically.

There are a few restrictions though - for PAE the PD must be below 4 GB because CR3 still only holds a 32-bit address, not a 36-bit address (like the rest of the paging structures when PAE is used).

The other restriction is when you're enabling long mode, and (usually) can't access anything above 4 GB until some initial paging data structures are created and long mode is enabled (even though CR3 becomes 64-bit when long mode is enabled).



You could have one big stack of pages, but...

If you support SMP, then it can be good to have lots of free page stacks with a seperate re-entrancy lock for each free page stack - it reduces lock contention when 2 or more CPUs are trying to allocate or free physical pages at the same time (and improves scalability).

If you support PAE or long mode, then you'll want one stack of free pages for RAM below 4 GB and another stack for RAM above 4 GB.

If you support page colouring, then you'll need one stack per page colour.

If you support NUMA, then you'll want one stack per NUMA domain so that you can allocate pages that are "close" (or faster to access) to the NUMA domain they'll be used on.

If your OS guarantees that newly allocated pages are filled with zero (e.g. so that if an application frees a page full of passwords another application can't allocate the page with the passwords still in it), then you can postpone the work of filling the page with zero by having a "dirty page stack" and a "clean page stack", where the OS takes pages from the dirty page stack, fills them with zeros and places them on the clean page stack when it has nothing better to do. The same system can also make it easy to support RAM testing (e.g. test if a page contains faulty RAM as part of filling it with zeros to improve the chance of detection and recovery if RAM becomes faulty while the OS is running).

If you combine all of this, then a system with 8 GB of RAM, 16 NUMA domains, 256 page colours and seperate dirty/clean page stacks could end up with 16384 seperate free page stacks....

You might also want to limit the number of free page stacks to prevent it from becoming excessive. A good way to do this is to limit the number of page colours so that "NUMA domains * page colours <= 256" (which gives a maximum of 1024 free page stacks after you add seperate clean/dirty stacks, and seperate above/below 4 GB stacks). A better way is to limit the number of page colours so that "NUMA domains * page colours <= N" (where N is determine by the amount of RAM the computer has).

BTW it is possible to write a physical memory manager that supports all of this, that also auto-detects how many page stacks to have during boot (based on number of CPUs, number of NUMA domains, CPU cache sizes, etc).

Lastly, don't forget that it's impossible to allocate contiguous pages with free page stacks, and that you may need to be able to allocate contiguous pages for ISA DMA and some PCI devices. Because of this I use a bitmap for memory below 16 MB in addition to all those free page stacks for memory above 16 MB....


Cheers,

Brendan

A important part is still missing and this known by the name of Identity Mapping, which means that when allocating special pages such as a Page Directory or Page Table they have a virtual address that is identical to their physical address in RAM.

The problem with not doing a Identity Mapping for these special pages is such that, take for instance:
VMMDIR g_k_dir = vmm_CreateDirectory();
vmm_Map(g_k_dir, KERNEL_OFFSET, KERNEL_OFFSET, KERNEL_SIZE/4096);
vmm_Map(g_k_dir, KERNEL_STACK_OFFSET, KERNEL_STACK_OFFSET, KERNEL_STACK_SIZE/4096);
vmm_On(g_k_dir);
Alright after doing this the kernel is running happily using virtual memory, no problem right? If so then let us try to map our VGA memory after activiating virtual memory.
vmm_Map(g_k_dir, 0xb8000, 0xb8000, 1);
It crashes... Why? We never mapped the directory or tables into our address space. It would seem obvious to just make a call such as:
vmm_Map(g_k_dir, (uintptr_t)g_k_dir, (uintptr_t)g_k_dir, 1);
This is great, now it crashes again because it allocated a table using physical memory but did not map it to the virtual memory we are running in. We need a automated way to identity map these special pages used for Page Directories and Page Tables.

The problem with identity mapping is that the exact same physical page address may not be free in every virtual space (multiple directories). The only way to do this dynamically is to force swap pages, or statically is reserve chunks/regions of memory for this special purpose (which I find very cumbersome). I am a flexibility freak I guess!

The idea is to store physical memory in a tree structure exactly like the Page Directories and Page Tables. We can make some utility functions to unify this abstract data structure between the PMM and VMM.

Utility Functions For The Abstract Tree
typedef uint32_t* MTREE;
MTREE mtree_Create(uintptr_t page);
uintptr_t mtree_Set(MTREE allocTree, MTREE tree, uintptr_t page, uint32_t value, uint32_t special);
uintptr_t __mtree_Set(uintptr_t *__freePage, MTREE tree, uintptr_t page, uint32_t value, uint32_t special);
uintptr_t mtree_Find(MTREE tree, uint32_t mask, uint32_t value, uint32_t rng_offset, uint32_t rng_stop, uintptr_t count);
uint32_t mtree_Get(MTREE tree, uintptr_t page);


This will create a new empty tree structure using one page.

This will access a entry in the tree using page as the address in the tree.

This will set a entry when standard memory management exists, by using a pointer to a value containing the address of one free page. This function will never need more than one free page per call, in some cases it may not even use the free page provided.

This will search the tree for a certain value that when masked equals it.

This performs the exact same function as the special __mtree_Set, except it uses a tree to find free pages to create tables when needed.

The New pmm_Free Using The Tree

This is our pmm_free function written to use the abstract data structure mtree, which provides us with a dynamic way to account for memory using a tree and unifying the abstract data structure between our pmm_* and vmm_* which saves overhead, work writting redundant code, and the possibility of introducing bugs through two seperate implementations of the same abstract data structure.

The Ability To Make Identity Pages Dynamically
typedef MTREE VMMDIR;
typedef uint32_t VMMREGION;
#define REGION_4MBOFFSET(x) (x>>16)
#define REGION_4MBSTOP(x) (x&0xFFFF)
VMMDIR vmm_Create();
uintptr_t vmm_AllocIdentity(VMMDIR dir, VMMREGION region);
uintptr_t vmm_Alloc(VMMDIR dir, VMMREGION region, uintptr_t count);
uintptr_t vmm_Alloc(VMMDIR dir, VMMREGION region, uintptr_t page, uintptr_t count);
void vmm_Map(VMMDIR dir, uint8_t region, uintptr_t phy, uintptr_t virt, uintptr_t count, uint32_t flags);
void vmm_Free(uintptr_t page, uintptr_t count);


Ok.. I just got really tired of doing this.. and realizing no one is going to read or understand all of this. ^_^

i prefer "the weird fractal mapping" trick myself

basically, you map the page directory into itself, so that the page directory acts as both a page directory for the current address space and the page table that maps its own page tables into that very address space

confused yet?

example: the page directory lives at 0x10000, if we set the last entry of that PD to 0x10000 (plus flags, of course), it will make every page table in the PD accessible through virtual addresses 0xFFC00000 - 0xFFFFFFFF because a page table maps 4 MB, and the page directory itself will be mapped at 0xFFFFF000 (because it is the last entry of our page directory now acting as a page table)

it takes some time to wrap your head around it, but its very elegant once you have it all worked out

you will need more than one PD mapped in most of the time, though
i keep the current address space, the "dummy" (never used after booting) empty kernel address space and a temporary spot (for when you need to change another process' page tables) mapped at all times

of course, this means you have to reserve some part of memory for all this (12 MB of virtual space isn't all that bad though), and you also need to make sure you've got your TLB invalidations right (simply because you're mapping/unmapping page tables to the same virtual addresses)

Oh. Yeah. I forgot a wrote a tutorial on that one.
http://kmcguire.jouleos.galekus.com/dok ... ace_scheme

Yes, Aali explained it correctly. The only difference in what I was doing (above) dubbed forcing physical pages to become swapped is to prevent you from having to reserved a certain range of memory just for the identity mapping.

So then you have 4096 bytes (a page) and the first 4 bytes of this page can't be overwritten (they're protected) and the other 4092 bytes are writeable for user applications or the kernel?
If so, could you tell me how this can be done? I thought you could only set protection on a whole page.



Yes. But to allocate it dynamically, should there already be some PD?



Thanks for the explanation above.
But why not use a stack for memory below 16MB?



Don't you need to use "INVLPG" in your pmm_Free() function?

Hi,



The pages are "free", which means they aren't mapped into any address space, and therefore can't be accessed at all. The kernel itself can't easily access the free pages, but it doesn't need to - it knows the physical address of the page on the top of the stack, and can find the physical address for the second page on the stack when it allocates the first (and maps it into an address space). The same happens for freeing pages (store the old "top of stack" into the page, then remove the page from the address space and set a new "top of stack").



Not really - you'd only need some basic physical memory management code that's used to setup paging and then thrown away.



The hardware outside the CPU doesn't know anything about paging or linear addresses. This means that for ISA DMA transfers and some PCI bus-mastering devices, you have to use contiguous pages to transfer more than 4 KB. Free page stacks won't work because there's no way to make the pages contiguous (the order of pages on the stack ends up being the order that they were freed by what-ever had them last, which means you get "random" pages rather than contiguous pages). To make it worse, ISA DMA transfers can't cross a 64 KB boundary (and must be below 16 MB). For e.g. an 8 KB buffer can't use one page at 0x0000F000 and another at 0x00010000, even though the pages are contiguous and below 16 MB.


Cheers,

Brendan

Do you have a picture illustrating how this works? What is done with the 4 bytes at the start of a page that points to the next page at allocation time? Are they zeroed, aren't they needed anymore?



So how does it go? pmm_Alloc() uses the PD when a PD is setup, what else does it do when you use pmm_Alloc() for the first time to setup a PD?

EDIT: If you read Kevin McGuire's first reply to my topic start post, he says I was correct that the Physical MM kallocpage() function should map an address in the PT. So there should be a PT and PD first to use kallocpage(), but you say I can use kallocpage() to allocate memory for a PD? Please understand me in that I'm a little bit confused here and there, I don't really see the overall picture anymore of how the whole PMM thing goes and how to initialize it. Maybe someone can draw a picture?



So Tim's tutorial on MM is wrong? He says you could setup a second stack for memory below 16MB.

pmm_Alloc does not have anything to do with the page directory. It is the physical memory allocator. It hands out physical or actually memory pages. The address returned by it is the same value that would be used to access the start of that page if paging was not activated. It can be used to allocate the page for the page directory and page tables because paging does not have to be active for the function to work. You are confusing physical and virtual memory.