Bootstraping the Page Manager

[Firestryke31]

Well, getting GRUB to boot an ELF kernel isn't all that hard. Hell, it's probably one of the easiest parts of writing an OS. What I'm having a bit of trouble is getting everything set up after this point. I was hoping to get ideas (not code) from how other people get things set up.

I think one of the biggest thing's I'm having trouble with is that chicken-and-the-egg page manager. I need the page manager to save all of the GRUB data structures to survive setting up the page manager. I know I could use a region of the BSS as a temporary heap but the problem is I don't know how much space is used by all of the structures due to differences in computers. Once I can figure this out I'm pretty sure I can get some of the other problems solved.

So, how do you bootstrap the page manager in your OS? What do you like about the way you do it? What do you dislike?

[pcmattman]

I usually read in the data from the multiboot structures, using a function to add each page of the memory map to a stack/bitmap/whatever. Then I have a choice: I can save the multiboot information, which I usually do by copying it to a new page (which also means I know exactly where it is), or be happy with what I've taken and blow it away. It really depends on how much you need from the multiboot structures after setting up your page manager.

[Combuster]

In my multiboot header, I specify that the BSS lasts until the 2MB mark. this prevents GRUB from putting anything in there, and thus I can use it as free memory until the physical memory manager is initialized. Until this point, there's just an allocator that returns the next free page after the kernel's end; more isn't needed. At a turning point, the early heap is disabled, the data that was allocated merged with the kernel image, the rest is transferred to the physical memory manager. You can then at a later time "hotplug" the remaining memory.

Note that my kernel is pure ASM and a flat binary, if you use elf multiboot, you'd need to trick ld into generating a larger .bss section without it placing object files all over it.

[AndrewAPrice]

Since I need GRUB to load modules for my microkernel to be in anyway usable I can use the top of the last module's end to get the start of the free memory, then once the modules have loaded I mark anything above the lowest module's beginning address (assuming GRUB loads modules right above the kernel) as being free.

[AJ]

Hi,

In the latest incarnation of my kernel (when I was working on it...) I didn't use GRUB, but the following still applies. I set up as follows (you may consider this a bit long-winded):

1. Copy and Parse GRUB's (or the BIOS) memory map:
This is the only stage that has that "hackish" feeling, as you need some reserved space in your BSS. Reserve plenty of space - you are going to claim it back later...
Once you have copied the memory map in its entirity, write a small dynamic allocator that can add regions to the memory map on allocation. For example, firing my own bootloader/kernel system up as it stood in May (qemu)...

Code: Select all

;Original Memory Map
0x00000 - 0x9FC00: Free
0x9FC00 - 0xA0000: System
0xE8000 - 0x100000: System
0x100000 - 0x7FF0000: Free
;...ACPI Here....

;Memory Map after my allocator had played with it
0x0000 - 0xA000: Reserved By Stage 1 Loader and IVT (includes some sector buffers - custom type code 0x8010)
0xA000 - 0x39000: Reserved By Stage 1.5 Loader (includes buffers, stack and some other stuff - custom type code 0x8015)
0x39000 - 0x9FC00: Free
0x9FC00 - 0xA0000: System
; ...
0x100000 - 0x108000: Kernel space (dynamically allocated by stage 1.5 loader - physical address doesn't matter because paging is enabled before the kernel is ever called. Custom type code 0x8020)
0x108000 - 0x800000: Page frame structures, cached data and initial heap (dynamically allocated. Custom Type code 0x8030)
0x800000 - 0x7FF0000: Free
;...ACPI Here....

So basically, you mark regions on the memory map to show you where GRUB's structures are, where your kernel is etc... Try to page align everything, so round all memory regions pessimistically - if it's a "Free" region, always round to make it smaller. The function to do the allocations is surprisingly small. I have this code all in a stage 1.5 loader so that the memory used in doing this is reclaimed later.

2. Allocate free space for your page frame allocator.
Once you have done the above, simply work out how much space you need for your page frame bitmap / stack and allocate dynamically, remembering to mark this region on your memory map.

3. Allocate free space for the GRUB structures you want.
If you like, simply allocate one big area combining points 2 & 3 to make it easier to page these areas in above the kernel after paging is enabled. Copy the GRUB structures to this "heap"

4. Allocate free space for an initial kernel heap.
If you like, you can add extra free space to 2 & 3. You then have a ready-made kernel heap, which you do not need to regard as temporary, as it has been allocated dynamically.

5. Enable paging.
Page in the kernel along with the memory structures allocated in 2, 3 and 4. I would suggest at least writing the PDE's for kernel space at this point. Enable paging and you have the kernel heap allocated in 4 to play with before you will ever need to deal with a PFE.

Hopefully you will find the whole "chicken and egg" situation a bit more palatable knowing that the only static structure is the BIOS memory map. Even if you have a really big memory map, having a couple of pages of BSS reserved for it should be more than enough. Everything else is dynamic.

Cheers,
Adam

[gravaera]

Hi;

AJ's points are really good: you can got to the bank with those.

For my own kernel, I initialize the memory manager as the absolute first thing, right after paging is enabled.

The order of initialization is as follows, with assumptions stated where necessary:

1. I use a .__ksetupText, and .__ksetupData section set in my ELF to keep a set of code and data symbols that are linked to the kernel's absolute physical address so they can be executed in the absence of paging or any virtual translation system. The code in these sections simply uses pre-allocated space in the kernel ELF image to set up the kernel page directory and page tables.

The obvious advantage of this is that I don't generate a hardcoded set of page tables and page directories in ASM using 4MB large pages like the wiki entry does, so I'm able to support processors lower than an i686 (4MB pages are Pentium Pro upwards; There is no guarabtee that you won't be booted on one of the older 1586s without PSE support.), and have my page tables configured in C++ at runtime.

2. Still within the .__ksetup* sections, I can now, since all code and data so far has been coming from special sections, zero out my .BSS section manually, thereby ensuring that I have no dependencies on GRUB, then enable paging, and switch to a stack in the .BSS section.

3. Now I immediately have the Memory Manager start by producing two bitmaps of 4K frames: one for 0x0 to 0xFFFFF (1MB - 1), and another for 0x100000 to 0xFFFFFF (16MB - 1).

The assumption here is that my OS should not be booted on a computer with less than 16MB RAM. This is a safe assumption, since even on cellular phones, mp3 players, and PSPs and GBAs nowadays, they tend to have at least that much, so porting to embedded with that assumption isn't too unrealistic.

An advantage of making an assumption like this is that you can hard-allocate the space for the BMPs into the kernel image since a BMP to manage the first 1MB only requires 32B, and a BMP to manage the next 15MB (up to 16MB - 1) is only 480B, and you can have these placed into the .BSS section.

At this point I have a physical frame manager for all of the assumed memory on the machine, and I can dynamically allocate memory for critical operations from either the first 1MB of physical RAM, or the next 15MB up to 16MB - 1. (Realistically, though, the critical stuff that needs to be done before eventually doing a proper memory enumeration will only take up about a max of about 16 or 32 pages, so...)

The idea in this method is to make an assumption about how much RAM you can depend on, and statically place the required space for your memory management structures into the kernel. You can then have dynamic memory coming from your assumed 'safe' region, and use that to properly dynamically allocate BMPs or stacks or whatever you choose for the rest of RAM.

This is not actually as illogical as it sounds, since you can make such an assumption quite soundly I might add, for a microkernel.

*Shrug*. Hope I helped you somehow.
--gravaera.

[Kevin]

tyndur uses a bitmap for physical memory managment, so the tricky part for us is to find a free chunk of memory where you can place the bitmap. Basically we have two functions to enumerate memory areas, one for the free areas in the BIOS memory map passed by GRUB, the other one for reserved memory like the kernel, Multiboot modules, command line arguments etc. Enumerate means here that they get an index and return one memory area each time. This can completely run on the stack (on a quite small stack even).

The algorithms goes like this (simplified):

Code: Select all

foreach free_area in BIOS memory map:
    x = free_area.start
    foreach reserved_area:
        if reserved_area intersects x ... x + bitmap_size:
            x = reserved_area.end
            restart foreach reserved_area
    if x < free_area.end:
        return x
panic()

[FlashBurn]

The obvious advantage of this is that I don't generate a hardcoded set of page tables and page directories in ASM using 4MB large pages like the wiki entry does, so I'm able to support processors lower than an i686 (4MB pages are Pentium Pro upwards; There is no guarabtee that you won't be booted on one of the older 1586s without PSE support.), and have my page tables configured in C++ at runtime.

If I remembering right PSE is available till the 1st pentium.

The assumption here is that my OS should not be booted on a computer with less than 16MB RAM. This is a safe assumption, since even on cellular phones, mp3 players, and PSPs and GBAs nowadays, they tend to have at least that much, so porting to embedded with that assumption isn't too unrealistic.

If you say that it is possible that your OS will be booted on an old 586 it is also possible that this machine has less than 16mb ram.

To get back to topic. I use my own boot loader and have reserved the region 1MB-2MB for my kernel and its data. So when I "allocate" mem for my mem manager I only need to map the mem at the end of the kernel. Later when my PMM and my VMM is up and running I can "free" the rest mem between the end of the kernel (+ mem for my mem manger) and the 2MB mark.

[AJ]

Hi,

Correction to my post - I have suggested creating a static BSS to store the memory map and described it as hackish behaviour. For even more "correctness", you could search the BIOS memory map to actually find the location to store the relocated memory map in the first place

If you do this with your own boot loader, you can just directly parse the BIOS memory map. If you use GRUB, you will also need to confirm that you aren't allocating memory over one of your modules, so you'll need to check the multiboot structures first.

Cheers,
Adam

[gravaera]

The obvious advantage of this is that I don't generate a hardcoded set of page tables and page directories in ASM using 4MB large pages like the wiki entry does, so I'm able to support processors lower than an i686 (4MB pages are Pentium Pro upwards; There is no guarabtee that you won't be booted on one of the older 1586s without PSE support.), and have my page tables configured in C++ at runtime.

If I remembering right PSE is available till the 1st pentium.

It was introduced in the original Pentium processor, but it was only publicly documented by Intel with the release of the Pentium Pro.

The Intel Manuals also, in the revision from 1995, do not quote the PSE as one of the features. I don't have the revisions for any of the other older releases, so I can't say when they officially documented it for the Pentium. However, I saw in some vague archive of the linux documentation an indication that there do exist old Pentiums which do not implement the PSE. That statement above was not groundless.

The assumption here is that my OS should not be booted on a computer with less than 16MB RAM. This is a safe assumption, since even on cellular phones, mp3 players, and PSPs and GBAs nowadays, they tend to have at least that much, so porting to embedded with that assumption isn't too unrealistic.

If you say that it is possible that your OS will be booted on an old 586 it is also possible that this machine has less than 16mb ram.

If you read into my post, I never implied that the base processor for my OS on 32 bit x86 was a pentium. It is in fact the i686. I also don't remember stating that this was an exhaustive explanation of my Memory Manager's initialization process.

Actually, the only reason I do a lot of things in my kernel which bend over backwards to ensure that it would run on even a 386 at least until the CPU Manager has been initialized, is so that I can properly display a message telling the user that a better processor would be required.

This was also a general explanation of an idea; It wasn't meant to be taken statically as a method where you assume 16MB. You could assume 1 or 2 if you choose. Not a very good point to nitpick at, is it? Especially since you make an assumption that could be classed in the same bracket; just with less RAM.

All in all, though, good analysis .

Good luck with your project,
--'gravaera

[FlashBurn]

The obvious advantage of this is that I don't generate a hardcoded set of page tables and page directories in ASM using 4MB large pages like the wiki entry does, so I'm able to support processors lower than an i686 (4MB pages are Pentium Pro upwards; There is no guarabtee that you won't be booted on one of the older 1586s without PSE support.), and have my page tables configured in C++ at runtime.

If I remembering right PSE is available till the 1st pentium.

It was introduced in the original Pentium processor, but it was only publicly documented by Intel with the release of the Pentium Pro.

The Intel Manuals also, in the revision from 1995, do not quote the PSE as one of the features. I don't have the revisions for any of the other older releases, so I can't say when they officially documented it for the Pentium. However, I saw in some vague archive of the linux documentation an indication that there do exist old Pentiums which do not implement the PSE. That statement above was not groundless.

If I only had a 2nd floppy disk drive here, I could test it (at the moment I have pentium 90, 100, 120, 133, 150, 166mmx, 200mmx and 233mmx). I do all the testing stuff in my loader, so that my loader says that my os wont run on this pc, so I write my kernel w/o testing every piece of the hardware.

So, back on topic. If you use a bitmap allocator I would allocate the 128kb in the bss. So you wont have problems to find some mem for it.

[Firestryke31]

So, I went with a simple bitmap page allocator that is initialized second thing in my kernel (first being interrupts). It allocates from the end of available memory first, meaning drivers are more likely to get a <16M address if needed. It's bare minimum, and assumes 4k pages in a 32-bit address space without any of those fancy bells or whistles that might be there. Now I guess I could copy my kernel to pages allocated from that and mapped into the same location and run with it from there. Next I get to write my virtual memory manager!