OSDev.org

The Place to Start for Operating System Developers
http://f.osdev.org/

How does paging is working ?

http://f.osdev.org/viewtopic.php?t=27277

Page 1 of 3

How does paging is working ?

Posted: Mon Oct 21, 2013 3:58 pm
by Jane1991c
Hey, I have been reading some so far and I can't understand how x86's paging is working.

Let's take an example and hope you will be able to explain me it ;)

# Scenario 1
Our kernel is 590 bytes long. Kernel is loaded into 0xA000.
Page directory and page table with 3 records is being created (3*4KB=12KB).
CR3 is being loaded with proper value of page directory linear address.
Paging is active.
What now ?
I may put some data to these 12KB ? How to access it ? Or shall i copy my program (cs) or data segment (ds) there ? How and what for is it right there ?

# Scenario 2
Let's say I have 3 tasks: task0, task1, task2
Task0 is being loaded (by LTR instruction).
All 3 tasks have their own page tables created with such memory:
task0 -> 1 page = 4KB
task1 -> 3 pages = 3*4=12KB
task2 -> 2 pages = 2*4=8KB

Each TSS has defined CR3 with correct page directory entery.
All seems to be working fine (no exception ;).
TSSs has defined their own CS/DS segment and also EIP.

How paging is working here ? Is paging some free space memory to use (stack?) or what else may it be ?


Please describe me how "paging" is working, becouse atm i know how to implement it but i don't know how is it working at all... thank you very much!

Re: How does paging is working ?

Posted: Mon Oct 21, 2013 11:59 pm
by dozniak
Have you tried reading Intel manuals? You may try starting there.

Paging is merely a mapping device - it says "If you try to access virtual address X, which physical address Y, if any, you will actually access". It may prevent access based on many factors - your effective privilege level, absence of a page at given address, type of access (write to read-only page) and so on.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 12:05 am
by summersong
http://wiki.osdev.org/Paging
http://wiki.osdev.org/Page_Tables

In protected mode you have 2 levels:
1st (PD): 1024 records * 4 Mb = 4 Gb
2nd (PT): 1024 records * 4 kb = 4 Mb

Each record of PD is offset (dword) of PT table (1024 * 4 = 4096).
Each record of PT is offset (dword) in physical memory.

So, you can make a trick: your kernel is loaded at 0000:A000 (phys), but you can say, that kernel is loading to 0020:0000 (log = 2 Gb). Every apps loaded at different part of memory (phys), but they all loaded at 0000:0000 (log). To do that you need to have separate page table for each application.

For example:
TestApp page table:

PD=0010:0000
PT=0010:1000
PD[0]=0010:1000 // PD[0] = PT = 0010:1000
PT[0]=0010:2000
PT[512]=0000:A000 // kernel at 2 Gb

So, "mov [0],eax" (0000:0000 log => 0010:2000 phys).
And "mov [2*1024*1024*1024],eax" (8000:0000 log => 0000:A000 phys).
Some interesting features:
1. ring0 apps can access every pages, ring3 apps can access only pages with PG_USER flag. This can protect kernel from apps.
2. each app has own page table. This can protect one app from others.
3. auto-growing stack: you place the stack at end of 2 Gb (log) and don't set to the previous page (2 Gb - 4 kb) the PG_PRESENT flag (stop-page). When the stack exceeds 4 kb, you get PAGE FAULT exception and can allocate and map one more page for app stack.

Sorry for my english.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 12:58 am
by Jane1991c
PT[512]=0000:A000 // kernel at 2 Gb
Why 2gb ?
0000:A000 is physical, right ? Well 0xa000 is 40960 in decimal, so it's 4MB not 2GB. Where am I wrong ?
So, "mov [0],eax" (0000:0000 log => 0010:2000 phys).
And "mov [2*1024*1024*1024],eax" (8000:0000 log => 0000:A000 phys).
And this feature starts working immidiatly after setting right bit of CR0 register, right ?
And what about External fragmentation ? What if there is somephing like that:

PROC1 (using 12KB)
PROC2 (using 24 KB)
PROC3 (using 8 KB)
[FREE SPACE OF 6 KB]

PROC2 is being killed and there is like that:

PROC1 (using 12KB)
[FREE SPACE OF 24 KB]
PROC3 (using 8 KB)
[FREE SPACE OF 6 KB]

Now i want to run new PROC which is 28 KB. My memory is 50 KB (let's suppose).
I need to move memory upper like:

PROC1 (using 12KB)
PROC3 (using 8 KB)
[FREE SPACE OF 30 KB]

And now I am able to run new PROC

PROC1 (using 12KB)
PROC3 (using 8 KB)
PROC4 (using 28 KB)
[FREE SPACE OF 2 KB]

And what if i am doing with paging where address translation is active and i can not to access physical memory directly ?

How to deal with it ?

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 1:36 am
by summersong
I was wrong.

Code: Select all

PD     = 0010:0000
PT_0   = 0010:1000
PT_2G  = 0010:2000

PD[0]   = PT_0  // page table 0000:0000 - 8000:0000 (0-2 Gb)
PD[512] = PT_2G // page table 8000:0000 - FFFF:FFFF (2-4 Gb)

PT_0[0] = 0010:3000
PT_2G[0] = 0000:A000
Yes, PT_0[0] and PT_2G[0] are phys.
And this feature starts working immidiatly after setting right bit of CR0 register, right ?
CR3 = page table
CR0 = CR0 or CR0_PM
And what about External fragmentation ?
Your memory manager will have 2 stages:
1st: allocate phys memory
2nd: map phys memory

If you have 10 non-consecutive 4 kb page (10 * 4096) of phys memory, you CAN allocate 40960 bytes to app.
But if the app page table don't have a 10 consecutive free PT, you CAN'T map this memory.
i can not to access physical memory directly ?
Yes, you can't access by physical memory offset anymore, but you can make an identity maping (http://wiki.osdev.org/Identity_Paging).
How to deal with it ?
The memory manager abstracts the physical memory from the kernel and apps.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 2:03 am
by Jane1991c
Well I am sick at the moment, maybe it's the main reason why I can't understand idea of paging.

Please explain me it one more time...

Sample code of TSS1 (dunno if mistakes happened, just example of sample code ;):

Code: Select all

TSS1:
 mov ax, 1
 mov bx, 2
 mov [0780h], 12h
 cmp al, 'f'
 mov cx, 66h
ret
Let's say it is loaded into memory at address 0x8000 and ends at 0x80AB (let's suppose).

It needs 1 page (4KB). So what to do right now ?

TSS need to have defined it's own CS and DS segment in it's segment, how to deal it with paging ?

Shall I make PTE with base address of 0x8000 (where TSS1 begins) ? Or how else shall I fill PTE's ?

I was searching a lot about it, I can't understand main idea of that, please explain it for me, thanks for patient ;-)

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 2:40 am
by summersong

Code: Select all

// build page table (C syntax)
// map 0000:8000 phys -> 0000:0000 log
PD      = malloc(4096);
PT      = malloc(4096);
PD[0]   = PT;
PT[0]   = 0x8000;
PD[512] = KERNEL_PT; // kernel at 2 Gb

cr3   = PD;

// call TSS1 (asm syntax)
call 8:0 // code_segment : logical_offset
TSS need to have defined it's own CS and DS segment in it's segment, how to deal it with paging ?
TSS (Task State Segment) or task? You can have only one TSS per one AP (CPU). All tasks will have same CS and DS.

Task switching will be like that:

Code: Select all

Task * curtask;

void TaskSwitch(int &eip, int &esp)
{
  Task * newtask;

  newtask = GetNextTask();
  if (curtask != newtask)
  {
     // save EIP and ESP
     curtask.eip = eip;
     curtask.esp = esp;

     // restore EIP and ESP
     curtask = newtask;
     eip = curtask.eip;
     esp = curtask.esp;

     // load page table
     int cr3_ = curtask.cr3;
     _asm {
       mov eax, cr3_
       mov cr3, eax }
}

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 4:23 am
by Jane1991c
I don't understand what you have writen about tasks.

There is TSS (104 bytes long as far as I remember) that describes task.
Each task should have it's own TSS. TSS keeps such data as DS/CS address and EIP.
It keeps task state while switching to other tasks etc...

You have writen that there may be only 1 task and TSS active. How ?

Another question you didn't answer ;p -> TSS keeps data such as DS/CS address. Should CS/DS addresses be physical addresses that are beetwen range of paging ?

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 4:47 am
by sortie
Perhaps you should get a good book on operating systems design and concepts? That's good reading while sick. :)

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 5:13 am
by Jane1991c
sortie wrote:Perhaps you should get a good book on operating systems design and concepts? That's good reading while sick. :)

I have been reading it already, I know "a lot", but i can't understand concept of paging and that's why i am asking it here ;p

Please one good example. So far i imagine paging x86 as a abstract layer of somephing, dunno what.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 7:49 am
by summersong
There are many implementations to control the memory:
1. use one TSS for one task
2. use segment registers
3. use paging
.....

I'm talking about one of them. In this implementation TSS and segment registers don't use.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 8:11 am
by Jane1991c
summersong wrote:There are many implementations to control the memory:
1. use one TSS for one task
2. use segment registers
3. use paging
.....

I'm talking about one of them. In this implementation TSS and segment registers don't use.
Yes, I was trying to combine segments and paging, because so far I have read it's possible, but what are advantages of that way ?

I simply don't understand idea of mapping memory when CS/DS segments are needed. How mapped memory should be combined against to CS/DS segments ? No one didn't answer these questions so far...

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 8:44 am
by summersong
what are advantages of that way ?
Example 1: task1 alloc 4096 bytes each 3 second, and task2 do the same. How to make that task 1 has had no access to the memory of task 2?

Example 2: swap.
I simply don't understand idea of mapping memory when CS/DS segments are needed.
In most kernels GDT consist of 3 descriptors: 00 null, 08 code (0-4 Gb), 16 data (0-4 Gb). Do you realy need THIS?
In long mode segment register don't use.
How mapped memory should be combined against to CS/DS segments ?
GDT consist of 3 descriptors, CS always 08, DS always 16. And paging. And one TSS.

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 9:24 am
by Jane1991c
summersong wrote:Example 1: task1 alloc 4096 bytes each 3 second, and task2 do the same. How to make that task 1 has had no access to the memory of task 2?

Example 2: swap.
Use segmentation and make limit for it ?

What if I don't want to use virtual memory (swap) then may I use only segmentation, with no paging needed ? Or is it needed in some way ?

summersong wrote:In most kernels GDT consist of 3 descriptors: 00 null, 08 code (0-4 Gb), 16 data (0-4 Gb). Do you realy need THIS?
In long mode segment register don't use.
Well i need to use segmentation, task segments etc... so what then ? Paging is useless here ? Do you mean by "long mode", a flat memory model ?
summersong wrote:GDT consist of 3 descriptors, CS always 08, DS always 16. And paging. And one TSS.
You mean in flat memory model, right ?

Re: How does paging is working ?

Posted: Tue Oct 22, 2013 9:41 am
by summersong
There are many implementations to control the memory. I think now you understand what is paging and how it's working. Use paging or not is your choise.
All times are UTC-06:00
Page 1 of 3

Powered by phpBB® Forum Software © phpBB Limited