How does paging is working ?

[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!

[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.

[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.

[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 ?

[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.

[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

[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 }
}

[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 ?

[sortie]

Perhaps you should get a good book on operating systems design and concepts? That's good reading while sick.

[Jane1991c]

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.

[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.

[Jane1991c]

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...

[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.

[Jane1991c]

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 ?

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 ?

GDT consist of 3 descriptors, CS always 08, DS always 16. And paging. And one TSS.

You mean in flat memory model, right ?

[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.