Paging, yes I read the wiki

[brodeur235]

In the page table, each entry points to a physical address that is then mapped to the virtual address found by calculating the offset within the directory and the offset within the table.

First of all, "mapping" and it's variations are words that are thrown around freely that I can't find a concise explanation for. What does it mean? If I "map" one address to another, what have I done and what will result from this? Commented asm code makes for great explanations if you have the time.

Assuming I know what "mapping" means, how do I find the afore mentioned virtual address once I have "calculated the offset within the directory and the offset within the table." By my count, after I have "calculated" these two offsets, I know have 2 numbers. What do I do with them to find the virtual address?

Also, by my rough math I'm understanding that there can be a max of 255 page table entries in the page directory, and 255 pages in each page table. Is this right? My reasoning is that the 20 bits used to address a page table / page can address up to 1023 kilobytes, divided by 4 (for each continuous page table / page address space) is 255.

All help is appreciated,

Brodeur235

[Firestryke31]

First, on a PC compatible x86 system, a page is 4096 bytes. This, divided by 4, is 1024 entries per table/directory.

Paging works like this: You have a virtual address, and this virtual address is taken by the hardware, and split up into a few indexes. The first part on a 32 bit system is which page table in the page directory to look in. The next index is which page in the page table to look in. The last index is which byte(s) to look at in the page.

Next, when we say "mapping," it means when the computer wants a virtual address, it gets redirected (mapped) to the physical address you say. Mapping is the process of telling it how to redirect (and the term can be used for more than just paging, but the concept is the same).

[System123]

Ok its a long time since I worked on my OS but lets see if I still remember.

Each Page directory contains 1024 entries, each of these entries maps to a page table which contains 1024 entries. These entries are the pages. Each page maps a certain section of memory. ie: the 1st page table maps the area of memory from 0x000000 to 0x100000, in 4Kb sections. The page tables can map physical memory to virtual addresses o it can just map physical to physical.

ie: 0x100000 = 0x100000 or 0xC0000000 = 0x200000 this depends how you choose to do this.

I think I am more or less correct on this

[skyking]

Did you read the MMU wiki page? The MMU translates from virtual to physical address, this is what mapping means. The wiki also says that there are 1024 entries is the both the page directory and page table. Basically when the software wants to access memory the top 10 bits is used as an index into the page directory where the entry is used to find a page table and the next 10 bits is used as an index into the page table, the page table contains the address to the page (20 bits) that together with the lower 12 bits of the virtual address forms the physical address which is used to access the memory.

IIRC the intel manual covers this in more detail.

[JamesM]

Hi,

Multiple explanations are always good, as long as they aren't contradictory - so here goes.

'Mapping' in the mathematical sense is the creation of a relation between members of two sets. For two sets (A, B), the mapping f(A) 'maps' a value from the set A to a value in the set B. In mathematical terms:

For two values a ∈ A, b ∈ B, f(a) = b.

The function 'f' can in this sense also be termed a 'relation', and can be written in the more friendly manner:

f : a → b

Here we can see easier that f 'maps' a to b.

-------------------------------

OK, mathematical interlude over (I hope that answered your first question, by the way!), time to apply it.

Forget about 'page tables' for the moment. Just think about the function 'f' above. Above, it mapped something from set A to set B. Now, think about it as mapping addresses from the "virtual" set to the "physical" set.

The "physical" set represents the actual addresses that get put on the computer's address bus, so it includes all RAM and memory mapped devices. This is the address space you are used to if you have used asm without paging.

The "virtual" set of addresses is made up. The idea is that a program (the kernel and all other application programs - basically *everything* once paging is enabled) doesn't need to care about how physical memory is layed out. There may be holes of unusable address space or memory-mapped devices, and also every program would be able to trample data and code from other programs and the kernel!

So code in paging mode see a "virtual" address space. This is (excluding if segmentation is also used) a clean, 32-bit address space extending from 0-4GB (on 32-bit x86).

The kernel is then free to decide how the addresses it writes to and reads from (virtual addresses) map to physical addresses. It uses a function to do this.
Remember from above that a function can be defined as a series of relations:

f : a → b, c → d, e →f, e → g

So 'f' can be defined simply by a table of all possible inputs and their associated output (if any). In this case, this is called a page table. All we need is a way of defining the function 'f' and to define what the inputs and outputs of it are.

Defining what each address maps to would require a lot of memory, so instead all systems divide the addressable range into fixed-size chunks called "pages", which on 32-bit x86 (without PSE) are 4KB, 4096 bytes in size. It is these pages that are the inputs and outputs to the mapping function. It takes as an input a virtual page number, and gives as output a physical page number. Please note that a virtual address may have no associated physical address. This is completely valid behaviour, and it is expected that the processor catch this and cause a fault.

Even though the addressable range (0-4GB) is split up into 4K pages, that still leaves 4GB/4KB=0x100000 virtual → physical relations to store. Each relation needs 32-bits storage (for the physical page, 20bits, plus 12 bits of flags), so that's 4MB to store all the relations.

That's a lot, and it is entirely possible that large expanses of the address space are unmapped - so we're basically wasting a lot of memory. Remember that in an operating system each process can have its own address space so it can't mess up others' data, so that's 4MB per process! Because of this, intel decided on a two-level page table system.


That image is copyright James Molloy, i.e. me, so I can use it without fear of reprisal

At the top is the "page directory". This is one page large (4KB), and contains pointers to "page tables". Each pointer requires 32 bits, so 1024 page tables can be stored in the directory.

The "page table" is again 4KB large and contains the relations mentioned above, 32-bits for each, so 1024 "page table entries" per page table. In total, that's 1024*1024=0x100000 page table entries available, which is correct for covering 4GB of address space.

Let's say you want to find the page table entry for the virtual address "0x12345000", so page number "0x12345" (remember that addresses given to the page mapping function must be aligned on 4KB boundaries, so the last three digits of a hex address must be zero).

You'd first calculate which page table the address lies in. Each table holds 1024 entries, so 0x12345 / 1024 = 72.8173828. Thus, our entry is somewhere in the 72nd page table.

Once we have the page table, to find the entry number inside it we can use a simple modulo: 0x12345 % 1024 = 837.

Once you have that page table entry, you can change which (if any) physical address the virtual address "0x12345000" maps to, along with some access privilege flags. See the intel manuals or the wiki for more information about that

I cover this in more detail and possibly less maths if that interests you here.

I hope this answers your question, if not please reply and let me know.

Cheers,

James

[brodeur235]

First off I want to say that that helped a ton James Molloy, so when I ask the few questions that I'm about to, it's not because your explanation was bad, but because I'm noticeable slow.

Even though the addressable range (0-4GB) is split up into 4K pages, that still leaves 4GB/4KB=0x100000 virtual → physical relations to store.

My math MUST be wrong somewhere because I do find that 1024 page tables * 1024 page table entries = 0x100000 virtual->physical relations, but no matter how many times I divide 4Gb/4Kb, I get 0xF4240. My reasoning:

4Gb * 1000Mb/1Gb = 4000Mb * 1000Kb/1Mb = 4000000Kb / 4Kb = 1000000Kb = 0xF4240

Also, just two questions on paging theory/technicalities:

(1) Because the address bus can only handle 32 bits is it impossible to have more than 4Gb virtual memory? (just making sure. In the meantime, I'm assuming that that's correct).

(2) Assume that I have paging enabled. Also assume that I have multiple virtual addresses mapped to one physical address (I assume you can do this). At this point, say for argument's sake that a program tries to access some random page in it's virtual memory. Does the CPU or the MMU handle moving the data at the requested virtual address page to the mapped-to physical address page before actually redirecting th program to the phyiscal address? (If I've worded this poorly and it's too hard to understand, please let me know and I'll rephrase it).

This is a pretty cool concept once you get a handle on it. I really didn't want to begin full scale development on my OS, without this feature, knowing that at some point it might become necessary to display an "out of RAM" notification, which is unquestionably lame. Again, thanks for the help to everyone who took the time to reply, especially JamesM. All help is appreciated,

Brodeur235

[pcmattman]

4Gb * 1000Mb/1Gb = 4000Mb * 1000Kb/1Mb = 4000000Kb / 4Kb = 1000000Kb = 0xF4240

There's 1024 MB in a GB, and 1024 KB in a MB:

4Gb * 1024Mb/1Gb = 4096Mb * 1024Kb/1Mb = 4194304Kb / 4Kb = 1048576Kb = 0x100000

[Walling]

(1) Because the address bus can only handle 32 bits is it impossible to have more than 4Gb virtual memory? (just making sure. In the meantime, I'm assuming that that's correct).

The linear addresses are 32 bit wide and so you have 4 GB virtual memory (on x86 in pmode). But the physical memory bus might not be limited in this way. That's why PAE exists. With 36 bits on the physical memory bus you can map your 4 GB virtual memory to 64 GB physical memory. This however slightly changes how you setup paging. You can lookup the diagrams in Intel Manual 3A.

(2) Assume that I have paging enabled. Also assume that I have multiple virtual addresses mapped to one physical address (I assume you can do this). At this point, say for argument's sake that a program tries to access some random page in it's virtual memory. Does the CPU or the MMU handle moving the data at the requested virtual address page to the mapped-to physical address page before actually redirecting th program to the phyiscal address? (If I've worded this poorly and it's too hard to understand, please let me know and I'll rephrase it).

Yes, you can map multiple virtual pages to the same physical one. You sometimes do that when you enable paging, because the instruction after enabling paging must be accessible to the CPU. Look up the Higher Half tutorial.

The CPU/MMU does not move any data, it just translates linear addresses into physical ones. I'm not sure I understood the question. If you're talking about missing pages, your OS has to take care of that. Fx. a program tries to access some un-mapped virtual memory, a page fault occurs, which hands control to the OS, the OS maps the page (maybe after loading it from disk -- this is swapping) and hands back control to the program.

[brodeur235]

Walling thanks. Yes, I was talking about "swapping," I just didn't know the term for it. Also, to maintain protected mode, is it common practice to setup a page directory for every process? If it is, then do you have to reset cr3 for every process? Help appreciated,

Brodeur235

P.S. pcmattman, could you not tell anyone I asked that question? Maybe we could even edit our posts to remove any evidence that it ever happened? JK, thanks for the help.

[skyking]

(1) Because the address bus can only handle 32 bits is it impossible to have more than 4Gb virtual memory? (just making sure. In the meantime, I'm assuming that that's correct).

No it's because the physical (address) bus only can handle 32-bits you have this limitatiation on the physical address, the limitation on 32 bits virtual address is that the registers only handles 32-bits data. Also the in physical address may not all bits be significant if there isn't pins enough for all the address bus (or all lines hasn't been routed on the PCB), but that's another story.

(2) Assume that I have paging enabled. Also assume that I have multiple virtual addresses mapped to one physical address (I assume you can do this). At this point, say for argument's sake that a program tries to access some random page in it's virtual memory. Does the CPU or the MMU handle moving the data at the requested virtual address page to the mapped-to physical address page before actually redirecting th program to the phyiscal address? (If I've worded this poorly and it's too hard to understand, please let me know and I'll rephrase it).

No, it translates the address. No memory is moving it just that the virtual address is translated to a physical address before it's put on the physical bus. If you access different virtual addresses mapped to the same physical address you will access the very same memory.

This is a pretty cool concept once you get a handle on it. I really didn't want to begin full scale development on my OS, without this feature, knowing that at some point it might become necessary to display an "out of RAM" notification, which is unquestionably lame.

No this feature is not required to display "out of RAM" notification. When you run out of memory you have to handle that anyway.

[whowhatwhere]

Hi,

Multiple explanations are always good, as long as they aren't contradictory - so here goes.

'Mapping' in the mathematical sense is the creation of a relation between members of two sets. For two sets (A, B), the mapping f(A) 'maps' a value from the set A to a value in the set B. In mathematical terms:

For two values a ∈ A, b ∈ B, f(a) = b.

The function 'f' can in this sense also be termed a 'relation', and can be written in the more friendly manner:

f : a → b

Here we can see easier that f 'maps' a to b.

-------------------------------

OK, mathematical interlude over (I hope that answered your first question, by the way!), time to apply it.

Forget about 'page tables' for the moment. Just think about the function 'f' above. Above, it mapped something from set A to set B. Now, think about it as mapping addresses from the "virtual" set to the "physical" set.

The "physical" set represents the actual addresses that get put on the computer's address bus, so it includes all RAM and memory mapped devices. This is the address space you are used to if you have used asm without paging.

The "virtual" set of addresses is made up. The idea is that a program (the kernel and all other application programs - basically *everything* once paging is enabled) doesn't need to care about how physical memory is layed out. There may be holes of unusable address space or memory-mapped devices, and also every program would be able to trample data and code from other programs and the kernel!

So code in paging mode see a "virtual" address space. This is (excluding if segmentation is also used) a clean, 32-bit address space extending from 0-4GB (on 32-bit x86).

The kernel is then free to decide how the addresses it writes to and reads from (virtual addresses) map to physical addresses. It uses a function to do this.
Remember from above that a function can be defined as a series of relations:

f : a → b, c → d, e →f, e → g

So 'f' can be defined simply by a table of all possible inputs and their associated output (if any). In this case, this is called a page table. All we need is a way of defining the function 'f' and to define what the inputs and outputs of it are.

Defining what each address maps to would require a lot of memory, so instead all systems divide the addressable range into fixed-size chunks called "pages", which on 32-bit x86 (without PSE) are 4KB, 4096 bytes in size. It is these pages that are the inputs and outputs to the mapping function. It takes as an input a virtual page number, and gives as output a physical page number. Please note that a virtual address may have no associated physical address. This is completely valid behaviour, and it is expected that the processor catch this and cause a fault.

Even though the addressable range (0-4GB) is split up into 4K pages, that still leaves 4GB/4KB=0x100000 virtual → physical relations to store. Each relation needs 32-bits storage (for the physical page, 20bits, plus 12 bits of flags), so that's 4MB to store all the relations.

That's a lot, and it is entirely possible that large expanses of the address space are unmapped - so we're basically wasting a lot of memory. Remember that in an operating system each process can have its own address space so it can't mess up others' data, so that's 4MB per process! Because of this, intel decided on a two-level page table system.


That image is copyright James Molloy, i.e. me, so I can use it without fear of reprisal

At the top is the "page directory". This is one page large (4KB), and contains pointers to "page tables". Each pointer requires 32 bits, so 1024 page tables can be stored in the directory.

The "page table" is again 4KB large and contains the relations mentioned above, 32-bits for each, so 1024 "page table entries" per page table. In total, that's 1024*1024=0x100000 page table entries available, which is correct for covering 4GB of address space.

Let's say you want to find the page table entry for the virtual address "0x12345000", so page number "0x12345" (remember that addresses given to the page mapping function must be aligned on 4KB boundaries, so the last three digits of a hex address must be zero).

You'd first calculate which page table the address lies in. Each table holds 1024 entries, so 0x12345 / 1024 = 72.8173828. Thus, our entry is somewhere in the 72nd page table.

Once we have the page table, to find the entry number inside it we can use a simple modulo: 0x12345 % 1024 = 837.

Once you have that page table entry, you can change which (if any) physical address the virtual address "0x12345000" maps to, along with some access privilege flags. See the intel manuals or the wiki for more information about that

I cover this in more detail and possibly less maths if that interests you here.

I hope this answers your question, if not please reply and let me know.

Cheers,

James

This.

Thank you JamesM. It's this sort of post I really appreciate reading.

[brodeur235]

Burning questions:

Can you create a page directory for EACH process, so that each one thinks it has 4Gb memory, or do you just divide up one page directorie's virtual memory?

Also, is there a way to detect the amount of actual physical RAM?

Brodeur235

[ru2aqare]

Burning questions:

Can you create a page directory for EACH process, so that each one thinks it has 4Gb memory, or do you just divide up one page directorie's virtual memory?

Also, is there a way to detect the amount of actual physical RAM?

Brodeur235

Yes, you can (and should) create a separate page directory for each process. Yes, you also can share page tables between processes to implement shared memory. You can't share portions of the page directory, as it is exactly one page long, and that is the unit for paging.

For the second question, please read the wiki, I think it has been already covered.

[Walling]

Can you create a page directory for EACH process, so that each one thinks it has 4Gb memory, or do you just divide up one page directorie's virtual memory?

Yes, just change CR3 and the TLB is flushed. You can also enable global pages, so shared memory (and maybe the kernel space) is not flushed. This is what I try to do.

Also, is there a way to detect the amount of actual physical RAM?

Have you read the wiki yet?

Edit: A little too slow

[brodeur235]

VBox is aborting when I try to actually enable paging by setting cr3 with the address of the page dir and turning on the last bit of cr0. The following asm is in my kernel's main:

Code: Select all

	;this part works fine
	mov eax,0x000B8000
	add eax,(80*25*2)           ;where to begin page directory (right after vid-mem)
	mov DWORD [kl_page_dir],eax ;save this
	mov ebx,0x0000D000          ;map 0x00000000 virtual to this starting phyiscal addr
	call k_setup_paging
	
	;this part makes VBox abort the OS
	mov eax,[kl_page_dir]
	mov cr3,eax
	mov eax,cr0
	or eax,0x80000000
	mov cr0,eax

And here is the source for my procedure that sets up paging for the kernel:

Code: Select all

k_setup_paging:
	
	mov DWORD [kl_page_dir_addr], eax
	
	add eax,0x400
	mov DWORD [kl_page_table_addr], eax
	
	mov DWORD [kl_page_phys_index],ebx
	
	;FILL PAGE DIR
	mov ecx,0x400
	.create_page_dir_entry:
		push ecx
		
		;PAGE DIR ENTRY
		xor edx,edx                          ;will use edx for currect dir entry
		or edx,DWORD [kl_page_table_addr]
		or edx,0xF                           ;000000001111b
		mov eax,DWORD [kl_page_dir_addr]
		mov [eax],edx
		
		;FILL PAGE TABLE
		mov ecx,0x400
		.create_page_table_entry:
			
			;PAGE TABLE ENTRY
			xor edx,edx
			or edx,DWORD [kl_page_phys_index]
			or edx,0x3                        ;11b
			mov eax,DWORD [kl_page_table_addr]
			mov [eax],edx
			
			;setup for next table entry
			add DWORD [kl_page_table_addr],0x4
			add DWORD [kl_page_phys_index],0x400
			
			loop .create_page_table_entry
		
		;setup for next dir entry
		add DWORD [kl_page_dir_addr],0x4
			
		pop ecx
		loop .create_page_dir_entry
	
	ret

;data

kl_page_dir_addr dd 0x00000000
kl_page_table_addr dd 0x00000000
kl_page_phys_index dd 0x00000000

kl_page_dir dd 0x00000000

What's up with this? All help appreciated,

Brodeur235