Paging..

[Kim]

For your init code you don't need a physical manager, just pick some free memory and use it as free pages. Later when your init code isn't needed anymore you could unmap it and use it as free pages.

Some test code i wrote, please note this code doesn't check if the memory behind the kernel is free to use (aka not a memory mapped device or something like that) kimage_end is the physical address of the ending of the kernel/init code section.

Code: Select all

   {Place page directory's physical page behind kernel}
   {kimage_end should be page aligned}
   page_dir := Ppd(kimage_end);

   {Initialize page directory, set non present flag on all entry's}
   for i := 1 to 1023 do
      page_dir[i] := 0;

   {Identity map first 1MB + kernel}
   image_page_table := Ppt(DWORD(kimage_end) + 4096);
   page_dir[0] := DWORD(image_page_table) or $3;

   for i := 0 to (DWORD(kimage_end) div 4096) - 1 do
      image_page_table[i] := (i * 4096) or $3;

   for i := (DWORD(kimage_end) div 4096) to 1023 do
      image_page_table[i] := 0;

Then after that you could map your higherhalf kernel into the addressspace. And enable paging and jump to it. And then initialize your physical page manager (provides physical pages for use in the virtual manager), virtual memory manager (gets the address of a free physical page and maps it at the wanted virtual address), kmalloc implementation (gets page size memory of the virtual memory manager and gives away chunks of it to some kernel code needing memory).

I hope its a bit helpfull and i didn't say to much idiot things

[ineo]

Just a question to the OS design experts: could you remember me why it is useful to have the kernel mapped in user process memory ?

I am gathering my pieces of code to do something coherent, and I realized I never asked myself why I did it (well I read it somewhere ).

Have you ever implemented a flexible memory model ? I mean one that will adapt to the architecture you are running on. I plan some testings on 64bit xeon, just for fun...

[Kim]

This piece of text from the intel docs will provide you with the answer

[tt]
5.12.1. Exception- or Interrupt-Handler Procedures
An interrupt gate or trap gate references an exception- or interrupt-handler procedure that runs
in the context of the currently executing task (see Figure 5-3). The segment selector for the gate
points to a segment descriptor for an executable code segment in either the GDT or the current
LDT. The offset field of the gate descriptor points to the beginning of the exception- or interrupthandling
procedure.
[/tt]

If an interrupt fires and you didn't mapped your kernel in the address space (only the interrupt handle realy needs to be mapped). You will get a pagefault because the cpu will try to execute a piece of code that isn't present in memory.

[ineo]

Well I remembered that, but I always wondered how to improve system calls (mostly speed, for IPC)... I always did it like others, because it works

But I am now thinking of providing a page to user process for that... and hide other things... I think I will be running into problems, again... but you know, it's the way it is.

[Warrior]

So basicly I need to check that memory I'm using as free to use as a starting point for my pages.
Only pages that are absolutely needed should be setup in the init, maybe some global pages or to setup a higher half kernel right?

The rest can be left to the rest of the kernel by having functions that pass the structure and using a pointer to the top of the memory set it up (Assuming you have structures for directory entries and table entries).

Then additionally you can return key things about page tables/directories as needed.

I think that's about right.

Another note: I don't get how a physical mm would be after all this is done.

Does a physical MM split memory into chunks and provide them as soon as the first chunk with sufficient space is found (or using another algo) but I don't get how it would tie in with my VMM?

THANKS A LOT for ALL your help.

[Solar]

I would suggest some reading from the thread "Book Recommendations", on OS theory. Once you got the idea on what the physMM does, you will need to know which pitfalls to avoid, and then it won't be long before you get to the point of scheduling algorithms... I learned a great deal from such books, and you probably don't want to create a mediocre OS either.

[AR]

I discussed this with GLNeo in http://www.mega-tokyo.com/forum/index.p ... eadid=8004 if you want to have a look

[Warrior]

Okay!

The virtual memory manager provides a list of free pages which the physical allocator grabs and maps the physical address to correct?

Now the elements of a physical allocator would be to "allocate" a page and map the address to it by finding a free paging and setting it to present right?

Now malloc()/free() are heap management functions but I'd have no idea where those would come in but assuming I'm right I feel like I have a better understanding of memory management.

[Warrior]

Sorry for the double post but I think I'm right so far and started implementing it.

I know Tim Robinson's tutorial mentioned maintaining a stack of free paging or using a bitmap.

I was wondering, why not have a variable holding the next free page and then have a function to request the free page and return that variable and set the next one?

[Brendan]

Hi,

I was wondering, why not have a variable holding the next free page and then have a function to request the free page and return that variable and set the next one?

That'd be perfect if all you ever do is allocate pages, but unfortunately you need to be able to free the pages sooner or later too.

Imagine you've got a pile of pages allocated - for e.g.:

AAAAAAAAAAAAFFF

Then you free one leaving a gap near the start:

AAFAAAAAAAAAFFF

When you free this page you'd adjust the variable so it points to the new lowest free page. Now imagine you allocate 2 more pages - the first comes from the previously freed page:

AAAAAAAAAAAAFFF

But now, what is your variable pointing to? Your forced into search through the pages one by one until you find the next free page. This is where the bitmap approach is slower than other approaches (especially if you end up searching through hundreds of pages to find the next free one).

If you used "free page stacks" you'd never need to search through anything - it's always fast (rather than "fast if you're lucky"). The problem with free page stacks is that you can't choose which physical address/es to use, which can be important (e.g. for ISA DMA buffers that must be below 16 MB and can't cross 64 KB boundaries).

IMHO the best approach is to use both methods - a bitmap for pages below 16 MB and free page stacks for anything above 16 MB.

Notice I said "free page stacks" rather than just "a free page stack". That's because I also said "best" rather than "a better". It's a discussion for another time...


Cheers,

Brendan

[Warrior]

Sorry for the bump but what are the uses of page tables, really?
I mean I know a page tables holds pages but the only possible situation I can see creating a new one is for a new "ruleset" to be applied to pages? That is of course unless pages can have different things ie be Supervisor in a table marked as User.

If anyone could please enlighten me on this I would appreciate this.

[AR]

Pages can be marked as supervisor under a User Page Table, individual pages can be made write-protected (useful for COW [Copy-On-Write when running multiple copies of the same program, especially fork()]), it also allows finer grained page accesses (4096 byte pages). If you want you can use PSE (Page Size Extensions) where you only need the page directory without page tables but each page will be 4MB.

[Warrior]

Hmm PSE looks interesting but I still don't know why different page tables are needed in a page directory.

Would you need more than one Page Directory in a process? I don't think so because it allows you to have 4GB of virtual memory and I don't know what having multiple would do or if it's even allowed.

The intel docs provide the structures that I've implemented (untested) to allocate a page table entry and and an entry in the directory, now when I'm writing an additional layer ontop of that (virtual memory manager) is when questions on implementation arise.

[AR]

Ok, A page directory/table is a list of pointers, each pointer corresponds to a physical memory location, if you have only the page directory that gives you 4096/4=1024 entries. If there is 4GB of address space and only 1024 entries available to map it then you end up with 4294967296 / 1024 = 4194304bytes per page. 4MB pages are extremely cumbersome (how many programs do you know of that have 4MB binaries? COW would be quite difficult as well (one change and the whole 4MB has to be duplicated), also imagine how long it would take to swap/unswap 4MB to/from disk), those 4MBs are physically contiguous as well, if the process only uses a few hundred KBs of a page then too bad, you are forced to waste the rest of it even when other processes need more memory.

On the other hand having page directories point to page tables then to pages gives you 1024 page tables, each pointing to 1024 pages so you end up with 4294967296 / (1024*1024) = 4096bytes per page allowing more efficient use of memory, especially since the physical memory doesn't need to be contiguous.

An example of how 4MB pages can be very bad would be memory mapping 12 100KB files. That would use 48MB of both PHYSICAL and virtual RAM.

There is only one page directory per process, each process would have it's own Page Directory.

[OSMAN]

}}}}}}};
Theory, yes. But still not any example code for us newbies of how to implement paging. (From the beginning)
So, could anyone... please post it?