OSDev.org

Posted: **Fri Mar 31, 2006 12:48 pm**

I'm now implementing virtual addressing, using paging w/o segmentation. For now, I've written some macros to set up the page directory and tables, mapping addresses, find addresses, etc.

But I've got a question: Is it ok to just set up the page directory, fill in all 1024 page tables, but leave all page tables empty (no physical address, supervisor, rw, not present) and then map these pages as they're needed or is it required to have at least 4 or 8 MB from the beginning?

Posted: **Fri Mar 31, 2006 1:01 pm**

I'd say it's a waste of memory to have 1024 page tables doing nothing. It's easy enough to check for the present bit in the PDE before trying to write to the page table, that way you can allocate page tables on demand if need be.

During boot, I allocate enough page tables to identity map from address 0x1000 to the end of the kernel, then I enable paging. The kernel heap is then mapped on demand.

Cheers,
The Senaus

Posted: **Fri Mar 31, 2006 1:30 pm**

But the kernel is mapped first thing after enabling paging, isn't it? So, I could actually set all my PDE's to not present and then extend the mapper function so that it automatically checks if the PDE is set as present or not and then sets them up? Well, yes, that would be more memory-efficient; I could later on program a low-priority thread that checks for empty PDEs and frees them...

Posted: **Fri Mar 31, 2006 1:46 pm**

Candamir wrote: But the kernel is mapped first thing after enabling paging, isn't it?

No, the kernel must be identity mapped before you enable paging, otherwise the machine will triple fault.

Candamir wrote: So, I could actually set all my PDE's to not present and then extend the mapper function so that it automatically checks if the PDE is set as present or not and then sets them up? Well, yes, that would be more memory-efficient; I could later on program a low-priority thread that checks for empty PDEs and frees them...

That's a good idea. Plus it's easy enough to loop down the page directory freeing page tables when you kill a process.

Cheers,
The Senaus

Posted: **Fri Mar 31, 2006 1:51 pm**

Specifically, you can't run the code that constructs the mappings for the kernel if that code is not mapped itself.

OS development is all about solving the chicken & egg problem.

Posted: **Fri Mar 31, 2006 2:36 pm**

The Senaus wrote:
No, the kernel must be identity mapped before you enable paging, otherwise the machine will triple fault.

When talking of identity mapping, are you talking of the mapping that assigns a physical addresss to the exactly same virtual address?

So, the virtual addressing startup pseudocode would look like this:

Code: Select all

void paging_init()
{
     create_page_directory(); // Leaves all pdes non-present
     map_kernel(); // Identity-mapping
     enable_paging(); // address of pd in cr3, bit 31 in cr0 set
}

Is this code ok?

And BTW, I also must map the pagedirectory and pagetables themselves, don't I?

Is my definition of identity-mapping correct?

Posted: **Fri Mar 31, 2006 2:58 pm**

That code's fine.

Identity mapping means mapping a linear address onto the exact same physical address. This means you can use the same address before and after paging is enabled.

Some people wrongly use identity mapping when the mean mapping the kernel to a high address such as 0xC0000000.

Straight from the manual:

The physical address of the current page directory is stored in the CR3 register (also called the page directory base register or PDBR).

Remember that, CR3 is a physical address. Therefore the page tables themselves do not even need to be mapped (but if you ever hope to read or modify them they must be, since you cannot map them later if they are not mapped initially).

Posted: **Fri Mar 31, 2006 3:04 pm**

Your definition of identity mapping is correct, and your pseudocode is in the right order. Keep in mind that map_kernel() will need to know the start and end address of your kernel. Plus it will probably need to dynamically allocate page tables, so make sure you initialize your physical memory manager beforehand.

You will need to map the page directory somewhere, for a uniprocessor system I'd recommend reserving a page in the virtual address space to map the current PD. Also, reserve one PDE, and set the mapping to the page directory itself. This will map all page tables as if they were PTEs.

Cheers

PS - we have a race condition here

Posted: **Fri Mar 31, 2006 3:28 pm**

The Senaus wrote: Keep in mind that map_kernel() will need to know the start and end address of your kernel. Plus it will probably need to dynamically allocate page tables, so make sure you initialize your physical memory manager beforehand.

Thanks to your fast response (indeed a race condition ;D, thanks to The Senaus and Paul Barker). By dynamically allocating page tables, are you meaning that I should request chunks of 4k size of the physical memory manager when creating new page tables? Because that's what I'm doing until now.

And to now the start and end of my kernel, is there a possibility to detect these addresses at runtime? There was a thread about that a few days ago, and they did it by including a symbol in the ld linker script, but I thought the thread a little bit confusing and didn't understand it quite well, so I'll go over it again, unless someone's got a quick response

. And if I want to load modules with GRUB, are they loaden just behind the kernel or elsewhere?

You will need to map the page directory somewhere, for a uniprocessor system I'd recommend reserving a page in the virtual address space to map the current PD. Also, reserve one PDE, and set the mapping to the page directory itself. This will map all page tables as if they were PTEs.

So I just map the physical address of the page directory to any virtual address I like or must that also be identity-mapped? And do I also have to map the page tables, or only the page directory? This is somewhat part of my kernel mapping routine, isn't it?

And what happens if I want to map my kernel later on to the top gigabyte? Do I have to take measures at compile-time or can this be done at runtime?

Thanks a lot,

Candamir

Posted: **Fri Mar 31, 2006 3:36 pm**

Go look at the FAQ, dig up the ld manual (use 'info ld') and google about a bit. Everything about linker scripts is very well described. Try http://www.osdever.net/.

Posted: **Sat Apr 01, 2006 1:06 am**

Concerning the kernel start/end issue: Well, I looked at some old posts and I think I'll be able to do it. (GRUB loads my kernel at 1MB by default, doesn't it?) But what concerns me more than that is the chicken&egg problem. There are two paragraphs about that in Memory Management 1 from Tim Robinson, but honestly, I don't understand all of it and it seems to me that those paragraphs contain the solution. I'm talking of the first two paragraphs (actually, there's one other line before them) in page 3. Actually, I understand the first paragraph, but not the second one. I'm also under the impression that there are some typos and contradictions, but as I don't understand it, I'm not able to judge it. Nevertheless, it's obviously still a great tutorial, although it's a little bit tough for beginners like me... ;D

Here comes the problematic (to me) second paragraph:

Text (from Tim Robinson's Memory Management 1):

But putting the memory manager in the boot loader isn?t practical. We need to have the processor seeing
address 0xC0000000 as 0x100000 without enabling paging. Later, we want to enable paging and avoid
relocating the kernel. We can do this by fiddling the base addresses of the kernel?s code and data. Remember
that the processor forms physical addresses by adding the virtual address (e.g. 0xC0000000) to the segment?s
base address and sending that to the address bus (or, if paging is enabled, to the MMU). So as long as our
address space is continuous (that is, there?s no gaps or jumps) we can get the processor to associate any
virtual address with any physical address. In our example before, with the kernel located at 0xC0000000 but
loaded at 0x100000, we need a segment base address which turns 0xC0000000 into 0x1000000; that is,
0xC0000000 + base = 0x1000000. This is easy: our segment base address needs to be 0x41000000. When
we refer to a global variable at address 0xC0001000, the CPU adds 0x41000000 and gets the address
0x1001000. This happens to be where the boot loader loaded part of our kernel, and everyone?s happy. If we
later enable paging, and map address 0xC0000000 to 0x1000000 (and use a segment with base address zero),
the same addresses will continue to be used.

Posted: **Sat Apr 01, 2006 2:23 am**

I always thought the GDT trick (which is what I think that paragraph is describing) is a bit confusing and completely non-portable, so I wrote up the HigherHalfBareBones tutorial as an alternative. Something in the same spirit ought to work on other architectures that lack segmentation (although I haven't tried it).

The basic idea is that you have a pre-defined page directory in the kernel's static data (i.e. -- a global array of PDEs that is *not* dynamically allocated) that will map the first 4MB of the physical address space (which includes lower memory plus the kernel and its modules) using a 4MB page to a high address like 0xC0000000 (in my kernel, it's 0xE0000000). Then you link your kernel at that virtual address plus 1MB (since GRUB loads it at 1MB physical). The tricky part is the first handful of instructions in the kernel entry point (which must be written in asm) -- they must be hand-written to be position-independent. All those instructions do is load CR3 with the physical address of the pre-defined page directory, enable 4MB pages (it assumes your CPU supports PSE), and then enables paging.

From this point on, the kernel code and data is running happily with paging enabled, as long as it doesn't run off the ends of its 4MB page. So then the chicken & egg problem becomes: How do you initialize the physical memory manager without being able to touch memory outside that page? My solution involved a few steps.

First, I cheated a bit by assuming that the Multiboot memory map passed by GRUB would always be in lower memory and would always be less than a certain size, so I could just copy it from there into another buffer in my kernel's data area. This was pure laziness on my part -- I think it would be possible to copy it from anywhere by modifying the "pre-defined" page directory as required. You might need an extra page that you could use as a temporary page table to map things in, or you could just use 4MB pages.

Next, I use the memory map to initialize a "watermark" physical page allocator that uses a bitmap that is also in the kernel's data area (i.e. -- just another C global variable). This watermark allocator uses the bitmap to allocate frames from each "window" of the physical address space. It uses the GRUB memory map to initialize each "window" as it moves along. This just lets me avoid sorting the memory map and implementing a complicated allocator based on "diffing" the free list, reserved list, and list of modules & kernel areas, which I decided was less interesting and much more difficult to understand than a watermark allocator (probably more lines of code and less maintainable too).

The next step is for the linear memory manager to use that watermark allocator to create some initial page tables and map in enough space to initialize the "real" physical memory manager. This part I haven't implemented yet... having a full time job makes it hard to make progress on OS dev.

Hope this helps.

Posted: **Sat Apr 01, 2006 6:44 pm**

Why, yes, now I understood! Because in the entire document, I think there's no reference to the GDT. I mean, I thought I ought to know what's the segment base, but I simply didn't remember...

quite stupid, eh? But anyway, I've now looked at the Higher Half with GTD in the FAQ and basically understood everything (should have looked up things in the FAQ earlier, my fault) but these lines of code:

Code: Select all

        // Fills the addresses 0...4MB and 3072MB...3076MB of the page directory
        // with the same page table

        kernelpagedir[0] = (unsigned long)lowpagetablePtr | 0x3;
        kernelpagedir[768] = (unsigned long)lowpagetablePtr | 0x3;

I don't understand the need of mapping the kernel to two different virtual addresses. Is this required for the following comment to be still valid after setting the new GDT?

Code: Select all

unsigned short *video = (unsigned short *)0xB8000; // We could also use the virtual address 0xC00B8000

EDIT: Actually, would it be possible to _only_ use virtual addresses and so leave the bottom area for user apps?

Thanks a lot

Posted: **Sun Apr 02, 2006 4:03 am**

I don't understand the need of mapping the kernel to two different virtual addresses. Is this required for the following comment to be still valid after setting the new GDT?

Yep.

EDIT: Actually, would it be possible to _only_ use virtual addresses and so leave the bottom area for user apps?

I think so. Try it.

Posted: **Sun Apr 02, 2006 5:55 am**

I don't understand the need of mapping the kernel to two different virtual addresses. Is this required for the following comment to be still valid after setting the new GDT?

No. This is needed because the kernel is running in the memory 0-4mb physical and virtual and after these lines you make a jump to let the kernel run in 0-4mb physical and 3gb till 3gb+4mb virtual. After this jump kernelpagedir[0] can be set to 0.

OSDev.org

Virtual Addressing / Paging

Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging

Re:Virtual Addressing / Paging