Using paging

[Whodoo]

I?ve been reading some stuff about paging... but what do I use it for? I know it?s good cause you can change the read/write acess for pages but how do I use it? Is it something special I do when using adresses? Like if I want a pointer, do I have to specify what page to use and all that? Or do I still reach memory with the segments, and only use paging for changing access levels and so on?

[Curufir]

Maybe I'm being tetchy, but is it too much to expect people to RTFM before asking things (Section 3.6.2 of Intel Manual 3)?

Anyhow...paging (Assumed 4k pages).

First imagine your memory is divided up into pages of equal size.

When your processor wants to generate an address it first goes through this translation.

Linear Address = Segment Base + Offset

Next it finds the correct Page Table using the Page Directory using.

Page Table Base = (CR3 + 4*(bits 22-31 of Linear Address)

Then it finds the correct Page Table Entry using

Page Table Entry Address = (Page Table Base + 4*(Bits 12-21 of Linear Address)

Finally it use the Page Table Entry to form the final PHYSICAL address.

Physical Address = ((Bits 31-12 of the dword at Page Table Entry Address) & (Bits 0-11 of Linear Address))

***

Ok, enough technical.

What all this means is that although your application thinks it's running in a nice linear address space starting from 0x0, in actual fact the set of pages being used by the application can be anywhere in physical memory or simply not present at all.

This hugely simplifies memory management because you no longer have to allocate large contiguous sections of memory. Eg Just because an application is 4Mb big you don't have to look through memory and find a 4Mb sized hole to put it in, you can get away with just allocating it 1 page of real memory at load time and load the rest as and when it is required (The app would thrash like hell if you tried though ).

Hope that helps.

[Whodoo]

Thank you!
But how does my application know what pages it?s stored in? I mean suppose I have an application with 4 kbs of instructions and some kbs of data. The instructions and data will then be stored in different pages. But how is this working, how does the program knows where the rest of the memory is? All it knows is that the data-section comes after the code section?
I get the basic idea, but I dont really know how to use it

[Curufir]

Thank you!
But how does my application know what pages it?s stored in?

It doesn't. That's the whole point.

As far as the application is concerned it has got a smooth linear address space from 0->4Gb (Assuming a flat-memory model). All the paging details are taken care of by the OS.

I mean suppose I have an application with 4 kbs of instructions and some kbs of data. The instructions and data will then be stored in different pages. But how is this working, how does the program knows where the rest of the memory is? All it knows is that the data-section comes after the code section?

Simple Example:

Let's say I have an application with 4k of code, 4k of data that is linked together assuming a start address of 0x500000.

When my OS loads the program it creates a page directory and a page table (Only need one because the application is so small).

Every entry in this page directory is marked not present aside from one entry that corresponds to the address 0x500000 (This would be the second entry in the page directory because each entry covers 4Mb of address space). This entry will contain a the base address of the page table.

Every entry in the page table will be marked not present aside from the two entries that represent the addresses used in my application. These entries give the physical base address of the page. For the sake of argument we'll say the first entry has a base address of 0x1000 and the second has a base address of 0x21000 (Nice and far apart).

With the page directory and page table built the processor goes off and loads my application, with the first 4k being copied to the physical addresses starting at 0x1000 and the second 4k copied to the physical addresses starting at 0x21000. It loads the bases address of the page directory into CR3 and jumps to 0x500000 (Which is where I linked everything to at compile time).

So far so good.

The processor goes through the translation mechanism above. It first goes to the page directory and finds the appropriate page table for the address 0x500000, then goes to the page table and finds the appropriate page table entry, it then uses that entry to get the start of the page in physical memory. The end result of which is to translate the linear address 0x500000 into the physical address 0x1000.

So my program runs along for a little while, then has to read some data from my data section. For the sake of argument we'll say this address was compiled to be 0x501050.

The processor trudges back to the page directory and pulls out the base address of the appropriate page table. It wearily finds the correct entry for this address in the page table and uses the entry to determine the start of the page in memory. It then adds the offset into the page. The end result of this heroic action is to translate the linear address 0x501050 into the physical address 0x21050.

The program doesn't realise it has been fooled. It thinks that it is just reading the data from 0x501050, when in actual fact the data has been stored at a physicla address of 0x21050.

Truly this is a monstrous deception on our part ;D, flames and torment await, but it is useful and the essence of paging.

Hope that helps.

[Whodoo]

thanks, it really helped me

[Solar]

It's perhaps noteworthy that the brunt of all the work Curufir described so aptly is not done by a dedicated part of the processor, the Memory Management Unit (MMU). In earlier days, a MMU could even be a seperate chip (68k / 68851).

This is to say that it does not degrade system performance significantly to use paging.

[Whodoo]

Alright But the processor will then use paging for All types of adresses? E.g. when I set a pointer somewhere, the OS can make it point to a complete different location?

[Solar]

Hehehe... obviously you didn't really get the idea yet.

When paging is enabled, every address visible to an application is a logical address. No matter whether you take the address of a function (code), a variable on the heap, or something on the stack. Logical addresses everywhere.

Only the OS has access to the page tables, which map logical addresses (ranging from 0 to 2^32-1 for every individual process) to available physical RAM (and, optionally, hard disk pages).

You did write applications before, did you? For Linux, Windows, whatever? Chances are you worked with logical addresses and paging. Did it change anything for you? No. There you are.

[Curufir]

Alright But the processor will then use paging for All types of adresses?

If the paging bit is set then you have to use paging, which implies that you have to set up page directories/tables correctly. You can't just use paging when you feel like it, it's all or nothing (Aside from a freaky scheme where you keep turning it on and off. DO NOT DO THIS ;D).

E.g. when I set a pointer somewhere, the OS can make it point to a complete different location?

Yes, that's the point. Paging lets the OS dump application code/data in real physical pages wherever it likes. The application doesn't need to know where in physical memory its pages are being kept (Although a knowledge of the page size can assist with certain application optimisations). All it needs to know is that when it forms an address to some part of its code/data the correct code/data will be there. The application sees only the linear (Sometimes called virtual) address space. The OS can also see the physical address space, and manages the translation between the two.

The only time this can cause problems is when you actually need to use a specific piece of physical memory (Eg Video RAM), in which case it's up to your OS to make sure the mapping from Linear -> Physical works.

***

It's perhaps noteworthy that the brunt of all the work Curufir described so aptly is not done by a dedicated part of the processor, the Memory Management Unit (MMU). In earlier days, a MMU could even be a seperate chip (68k / 68851).

I admit I tend to just lump all these things together into the term 'processor'. I prefer leaving the magic smoke filled boxes to Electronic Engineers (If you've ever seen an industrial transistor blow then you know what I mean ).

[Whodoo]

Yes but what I mean was, that the OS can make a pointer point to a complete different location? For instance, suppose I got some information stored at 0xC0000. In my kernel I also got a function that will do something with this information, so I got a pointer, pointing to this location. But if I set up my pages wrong, it?s possible that it wont work cause the function will operate on an other memory location than I set it to in the code right? So I gotta be a little bit carefull, e.g. so if I load my kernel at a location (and loads the entire kernel in the memory with no gaps), bad paging can screw it all up?

[Solar]

With paging enabled, a user-space pointer always points to a logical address.

If you pass a pointer value from user space to kernel space - e.g. through a syscall - the kernel has to go through the paging mechanism to find out what physical address that logical pointer refers to.

[Whodoo]

thanks guys, been freaking over this for a time and didnt find something good to read ;D

[Whodoo]

But I thought of something..in multitasking..suppose my memory is like:

0x0 0x1000 0x3000
[Program 1] [Program 2] [Program 3]

Then I kill Program 2..and I wanna start a new Program... but that Program is much larger than Program 2 so I put a part of it where Program 2 was stored, and the rest after program 3 like

0x0 0x1000 0x3000 0xSomething
[Program 1] [Program 4 part 1] [Program 3] [P4 part 2]

when Program 4 runs I must "trick" the computer to believe that the memory location 0xSomething is 0x3000(because 0x3000 comes linear after the first part of program 4).. that?s no problem but what when Program 3 is running.. do I have to change the "remapping" everytime I switch a process? Or else the Program 3 would actually run on 0xSomething?

[distantvoices]

Now, keep in mind, that you deal with page directories and page tables, and that it *does not matter* where in physical memory the pages are located. Important is, that they are entered in the pagedir/pagetable to fease the translation from logical address to physical address.

regarding your question about processes:

First, you need something in your kernel land which deals out and takes back one thing: pages of memory - size=4096.

Second: have each process start at say virt: 0x1000.

Lets have the kernel at virt. 0xc0000000.

Now: we form a stack of free pages. Forget about the bitmap approach in the moment. We build a pile(actually an array) of adresses at some location. We fill it with adresses of physical pages, starting from max and until we reach page zero.

From this pile of free pages, we hand out pages of memory to the needing ones: Processes. A pagecan be: Page directory. Page Table. Page Table entry. So, mark: you deal out a page directory to a process. Fill in the kernel adress space. map in some user adress space: 0x1000 - 0x1fff. You deal out 3 page tables in total. for that: one page dir, one page table, one page table entry.

NOw, upon deletion of the process, you simply put the pages onto the stack. thats it. don't ever care too much about ordering them in the beginning.

you also don't care about *where* in physical memory newborn process 2 has its memory. You just take a page directory and fill in the adequate amount of memory pages.

Best is you take pencil and paper and draw a picture of how it works in your imagination. Do some good reads. There are plenty in the internet.

Stay SAfe.

PS: NO, I don't want to take a club ...