PAGING, a pain for ever

[kmtdk]

HI

I ask all of you.
can you describe how it works, how to calculate the base address of the table, and how it calculates the lineary address.

I cant figure it out,

thanks for the help

KMT

[Alboin]

1) Paging has been described millions of times before. Please do some searching. Thanks.
2) Which table? They can be pretty much anywhere in memory. (Granted they are aligned properly.)
3) (virtual address?) The virtual address if determined by the MMU, which checks the paging tables, and determines where your page is mapped in physical memory. It then uses that to do whatever it is that you are doing.

[kmcguire]

A Imaginary Machine Memory Bus Example
You should already know that a pathway between the processor and memory exists called the memory bus. This is where addresses are sent down pins and data is read or written to the memory by the processor. When paging is disabled the addresses are sent unmodified from the processor to the memory unit.

If our imaginary system has a memory bus with a ten bit address path and a ten bit data path then it would be depicted like so below. The lines are little electrical pathways.

Code: Select all

|`````|-----------|``````|-----ADDR0-------|````````|
|     |-----------|      |-----ADDR1-------|        |
| CPU |-----------| TLB  |-----ADDR2-------| MEMORY |
|     |-----------|      |-----ADDR3-------|        |
|     |-----------|      |-----ADDR4-------|        |
|     |-----------|      |-----ADDR5-------|        |
|     |-----------|      |-----ADDR6-------|        |
|     |-----------|      |-----ADDR7-------|        |
|     |-----------|      |-----ADDR8-------|        |
|     |-----------|      |-----ADDR9-------|        |
|     |           |      |                 |        |
|     |----CLK----|      |-----CLK---------|        |
|     |           |      |                 |        |
|     |-----------|      |-----DATA0-------|        |
|     |-----------|      |-----DATA1-------|        |
|     |-----------|      |-----DATA2-------|        |
|     |-----------|      |-----DATA3-------|        |
|     |-----------|      |-----DATA4-------|        |
|     |-----------|      |-----DATA5-------|        |
|     |-----------|      |-----DATA6-------|        |
|     |-----------|      |-----DATA7-------|        |
|     |-----------|      |-----DATA8-------|        |
|     |-----------|      |-----DATA9-------|        |
|     |           |      |                 |        |
|     |           |      |                 |        |
|_____|-----------|______|-------R/W-------|________|

You should notice that there are four major parts to the drawing. There is the ADDR pins which represent address pins between the CPU, TLB, and memory chip. A set of DATA pins exist. The CLK pin, and finally a R/W pin.

The CLK pin is just for illustration purposes and is actually beyond the scope of this informative post. The R/W pin is also just outside the scope, but I have included them in order to make a more detailed and informative example.

During a memory write the R/W electrical pathway is held in a high state; meaning that voltage is applied and it meets a level that is considered a logical value of one. This tells the memory chip that it shall write the value on the DATA lines to the address held on the ADDR lines. If a memory read is wanted then the R/W electrical pathway will be held low, or no voltage, logic zero state which will tell the memory chip that it should place the value at the address represented by the ADDR pins onto the DATA pins so that the processor may read it.

In order to synchronize this exchange of addresses and values through reads and writes a CLK electrical pathway exists. Communication with the memory chip is started when the CLK electrical pathway is a logical one (meaning voltage is applied). During this period that the CLK line is held high the address is placed on the ADDR pins and the R/W line is either taken high for a write or low for a read.

When the clock goes logic low the memory chip will read the address from the ADDR pins. Then if the R/W pin is a logic low it will read the location set by the ADDR pins and place the value on the DATA pins. If the R/W pin is a logic high then it will write the value on the DATA pins to the address represented by the DATA pins.

During execution the processor will constantly be flipping the clock line high and low in order to perform reads and writes with the memory chip. At this time the TLB has done nothing and will do nothing as lone as paging is disabled.

Lets talk a little about what the TLB does next, but before you continue make sure you understand what is going on in this part.

The TLB
TLB, stands for translation look aside buffer. It sits between the CPU and primary memory in general. It's job is to do nothing when paging is disabled, but once enabled it will start to translate addresses. The question is how does it know what to translate and if so how to translate it. We know that we will essentially be translating one address into another so we can answer the first question, but how does it know.

The TLB knows how to translate one address into another by using a paging structure. For the 80386 it is called a page directory and page tables, but in our example we are simply going to call it a paging structure.

Paging Structure
Since our imaginary system has a ten bit address path and a ten bit data path we are going to invent a really simple paging scheme. Each page in our system will be exactly 32 bytes. And, each byte in our system will be ten bits. I know that sounds really weird, but it is just important for this entire concept to make good sense.

Since our pages are 32 bytes it will take five bits to address anywhere inside a page. If you find the value of five bits in binary you will get the value 31 and using indexing starting at zero you will have 32 positions which represent the 32 bytes in a page.

Lets imagine for a moment that memory access in our imaginary computer used two registers. A segment register similar to real mode on the 80386 and a general purpose register.

So that:

Code: Select all

MOV MS, 1
MOV EAX, 22
MOV EBX, [EAX]

The above would access the twenty-second byte in the second page in memory. Since the first page would be zero! If we placed zero into the segment register MS then we would access the twenty-second byte in the first page in memory. If it does not make sense just think about it once or twice more!

Instead of using segment registers (like MS) in the example above we could just use general purpose registers on our CPU. This is possible because our registers in our CPU are the same width or larger than the address bus. In our system the registers, address, and data bus are all the same size so it makes everything easier to understand -- except the strange ten bit byte, haha.

So using just a register we could load the same address above like:

Code: Select all

MOV EAX, 22 + (32 * 1)
MOV EBX, [EAX]

Or, the very first page in the system with:

Code: Select all

MOV EAX, 22 + (32 * 0)

Take a long look at the effect of multiplying by our page size and you should see how the processor would have used the segment register in the very first example along with the register to get the
exact same effect we are getting now.

Lets break our addresses down into binary for a moment to better study this page addressing mechanism. If you remember our page size is 32 bytes, and to represent 32 bytes we need five bits. Well, in our system we have five more bits left. Lets take a look at ten bits:

Code: Select all

BBBBBBBBBB

Now, lets look at just the five bits which give us 32 memory locations (marked with the letter A):

Code: Select all

BBBBBAAAAA

That leaves five most significant bits. These give most significant bits are what (32 * x) uses. If you perform the equation (32 * 1) you will get the value 32. The value 32 in binary is:

Code: Select all

0000100000
BBBBBAAAAA

You should notice that the first one resides in the bits marked by the letter B above. The region of the address marked by the letter B above shall be called the page address, while the remaining bits which are make by the A is called the byte address.

Code: Select all

PAGE ADDRESS     BYTE ADDRESS
  00001             00000
  BBBBB             AAAAA

However, it is wise to note that the memory chip knows nothing of pages! The entire address is sent straight to the memory chip on the ADDR pins with out separating the A and B parts. The A and B parts are going to be separated by the TLB chip which sits between the CPU and memory chip. At the current time it has been doing nothing but acting invisible. The bits sent down the ADDR bus from the CPU went straight through the TLB chip unaltered and vice-versa for the memory chip. In the next section we will talk about what happens when the TLB is enabled (paging is turned on) and the bits are altered between the CPU and memory chip.

This addressing scheme enables you to specify both the page address and byte address while still treating memory as a long continuous stream of bytes. Now, that you understand how we will break our address space into pages we will explain how the TLB uses this to translate addresses for the CPU in the next section.

Translation
The TLB needs to translate a virtual address into a physical one. In order to do so it needs a map that tells it the physical address for any virtual address. We also need something to map and since we broke our address space into pages using the most significant bits in our address we can simply assign virtual pages to physical ones. To do this we will use one page to create our map. You should remember that one page has 32 bytes and each byte has 10 bits.

This will allow us to turn one memory page into a map. This page can be a map since we have a maximum of 32 pages in our system from the 5 left over most significant bits. This means we need 32 entries in our map. Each entry needs to be at least 5 bits. It just so happens that one page has twice the needed space to store the map of 32 five bit entires. But, just to keep things simple we will use 10 bit entries which wasts a few bits.

Once turned into a map the TLB would load this page into it's cache. The equivalent algorithm is shown below in a C function:

Code: Select all

uint10_t TranslateVirtualToPhysical(uint10_t *map, uint10_t vaddress)
{
	return map[vaddress >> 5] | (vaddress & 0x1f);
}

The function above takes a pointer to a map which is a page that is 32 bytes in length using 10 bit bytes. The vaddress argument is the address the CPU send via the ADDR pins. The address the CPU send via the ADDR pins is shifted to the right five bits. Lets take a look at our address scheme:

Code: Select all

BBBBBAAAAA

If we shift right we will shift all the A(s) out and zeros in on the left. This will leave the page address. Since the page address uses five bits we have a total of 32 pages in our system. In our map we need 32 slots or entries. Each slot or entry is a byte which on our imaginary system is 10 bits. These 10 bits are used to store a physical page address. We find the correct slot using:

Code: Select all

map[vaddress >> 5]

What is returned is the mapping of the virtual page address to a physical page address. Then we do:

Code: Select all

(vaddress & 0x1f)

This will turn the page address bits into zeros and leave just the byte address. After, that we combine
the translated virtual address with the left over byte address and we get a physical address.

Code: Select all

 map[vaddress >> 5] | (vaddress & 0x1f)

This address is sent to the memory chip transparently to the CPU. Meaning, the CPU does not see this translation taking place. The CPU thinks it is reading from the vaddress yet it is really reading from a translated address provided by the TLB.

Imaginary Machine Paging Conclusion
You have now seen an imaginary example of paging. I used this imaginary example to simplify the entire concept so that hopefully you can grasp what is happening on the 80386. I want to give a quick example of what paging might be used for using this imaginary system.

Lets say in our imaginary system we have a few programs running. Each program would like to have it's own 1024 bytes of memory and be protected from other programs. To do this we would create a map for each process. Creating a map for each process would require one page per process. In a real machine this would be quite limited with only 1024 bytes of total system memory because of a ten bit address bus, but since this is an example it will be okay.

Now, lets have a special instruction that loads the address of a map into the TLB chip and enables paging. This will allow us to change the map when we change processes. The image below depicts using multiple maps and providing each process with it's own address space.


There are five rows of boxes. The first row is space reserved on the hard disk for a swap file. The second row is physical memory. The last three rows are the address space for each process provided by their map page. You will notice lines going from boxes in each process to boxes in either the physical memory row or the disk row. When a line goes from a process to a page in the disk row it means that the page of memory for that process has been swapped out. If a page is swapped out and the process tries to access that location then some mechanism will allow the kernel to trade some cold page in physical memory with the page on the disk needed and remap then continue the process.

A page is cold when it has few accesses, and is hot when it is accessed a lot. The idea is to move cold pages into swap to make more room for hot pages. This allows you to exceed the installed memory on your machine by using some of the disk space as extra memory. We never discussed a mechanism for telling if pages are hot or cold in our imaginary machine. But, for example on the 80386 a dirty bit is set when a page is accessed and this is just an example of a method that could be used to find cold pages and swap them to disk.

The green squares are the kernel. You should notice the kernel is mapped in the exact same spot in all address spaces and physical memory. This can be beneficial if the process can raise interrupts and exceptions and the kernel needs to be in the same place each time. You should also notice a blue box in each process' address space. This blue box represents the page map for that process. As you can see each process has their own map page even though they are all the same color. You can verify this by noticing that there are three blue boxes in the physical memory row which represents the three map pages used by the processes.

If you find it a little hard to understand then just keep looking and following the lines in the picture!

80386 Paging
The paging on the 80386 differs slightly and is made a little more complex with more indirection. On the 80386 there exists the equivalent of our map page called a page directory. The added complexity is that each page directory points to page tables. This design in my opinion was used to decrease the memory consumption of the mapping structure while still providing small page sizes. The 80386 supports 4 gigabytes of memory using four kilobyte pages. This gives 1,048,575 pages in total. Our imaginary machine had 32 byte pages and used 5 bits to represent a byte address inside each page. On the 80386 each page is 4096 bytes and uses 12 bits to represent a byte address inside each page. Also to note is that 1024 pages on the 80386 make 4 megabytes.

The 80386 uses one single 4096 byte page to create a page directory. This directory has 1024 entires almost exactly like our map page which had 32 bytes which gave 32 entires. The difference is that each entry in the 80386 page directory is four bytes instead of one byte. This is because each byte is eight bits and it takes thirty-two bits to address anywhere in the thirty-two bit address space.

The reason they did not use less bytes like three since (32 - 12) is 20 bits which is all that is needed to reference a page in the system has to do with memory alignment and performance which is a little outside the scope of this article. So they used four bytes.

Unlike our imaginary system each entry in the page directory points to a page table. Or imaginary system used the first entry to point directly to the physical page. The 80386 uses the page table to point to individual physical pages. Each page table can map 4MB of memory. Each entry in the page directory point to a page table.

It is a little confusing but each page table also has 1024 entries just like the page directory. Each entry in the page table is also four bytes just like the page directory. Lets break down a thirty-two bit address into it's parts before we continue too much further:

Code: Select all

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCCC

Then splitting the parts up:

Code: Select all

Directory Index        Table Index         Byte Address In Page
  AAAAAAAAAA            BBBBBBBBBB           CCCCCCCCCCCC

As you can see we get a directory index, table index, and byte address in page. This seems almost exactly like our imaginary machine except for this added table index. What happens is that we do our normal lookup for an entry inside the page directory.

Code: Select all

directory[vaddress >> (10 + 12)] & ~0xfff;

This yields the address of a page table. You should notice a ~0xfff. This zeros the lower twelve bits. On the 80386 the least significant twelve bits are used for flags and things in the page directory and page table entires. There is also a PRESENT bit which indicates the the entry is enabled. When you write actual production code you must check this bit to determine if the table actually exists or is enabled.

After getting the address of the table. The TLB would then query the table entry for the physical address:

Code: Select all

table = directory[vaddress >> (10 + 12)] & ~0xfff;
return table[(vaddress >> 12) & 0x3ff;

So the 80386 works very similar to our imaginary machine except that it has an extra level of indirection. This indirection being the page tables after the page directory.

[Zenith]

Whoa.

You should add that to the wiki.

[JamesM]

@OP: I already pointed you to a resource that describes what you are asking, yet you replied that it didn't help you as you knew it all already.

So what exactly do you know, and what exactly don't you understand? Without asking a more detailed question you're very likely to hear the same things that you've already read and failed to understand repeated again.

Cheers,

James

[geppy]

So what exactly do you know, and what exactly don't you understand? Without asking a more detailed question you're very likely to hear the same things that you've already read and failed to understand repeated again.

check my posts in another thread started by the same guy. Thats what you tutorial is missing.
Every single tutorial jumps to describing flags and actually fail to do even this because Intel description of flags is excellent.

[JamesM]

Thats what you tutorial is missing.

I read your other posts and still can't quite work out what you're saying. What exactly is missing?

And yes, the intel manuals are excellent. So read them! No tutorial is aimed at replacing the content of the manual - it's meant as a 'quick start guide' of sorts.

Cheers,

James

[kmtdk]

Well JamesM,
as Geppy said, all tutorials on paging NEED describning on other things than the flag describing. Of cause the example code is good, but it dont cover all.
And the Manuals are greate, but they are not to easy to understand, but you get too much information.

So what i asked for was a good describning of the "last" part. ( after reading the big poster kmcguire layede here , and after reading Geppy last post in my previously thred, i got a lot far than i were before, but still )

KMT

[JamesM]

So what i asked for was a good describning of the "last" part.

Hi,

I take your point, but you still have to be a little more specific than this - what exactly does the "last" part encompass?

Once I know that, I can give you more, targetted, help.

Cheers,

James

[kmtdk]

Okay,,
a describing on: how the 20 bit addressing work, inside the page table, and dir table.
defining a page.
what to do after setting up paging, ( your code, does it location changes ??? or anything else.)
How can you then map all "running code" to 0x01000000, and still have diffrent dir pages. ?

Thanks a Lot

KMT

[geppy]

paging is one big lookup table converting fake linear address to physical addrs in RAM

how the 20 bit addressing work, inside the page table, and dir table.
defining a page.

I shall try one more time:
Page-Directory entry contains(points to) 4KB aligned physical address of entire Page-Table table
Page-Table entry contains 4KB aligned physical address of 4KB memory block called a "page"
thats all.

Do you know how to find correct entry # if you are given linear address?
Do you k now how to calculate addrs of the entry (if answer to previous is Yes)?
Do you know what to do with the addr?

Page-Table is 4KB memory block in RAM that contains paging info needed for CPU
Page-Directory is 4KB mem block in RAM that contains paging info needed for CPU
Page is memory block in RAM with which you do whatever you like

"4KB aligened" means every single address has lowest 12bits set to 0. Which in turn means that lowest 12bits in Page-Dir Page-Table entries are used for some other purpose - for flags.

what to do after setting up paging, ( your code, does it location changes ??? or anything else.)

Physical location of code doesn't have to change and normally you never change it.
Paging come usefull during memory allocation. say you have 4KB free at 200000h and 4KB free 300000h but user wants to allocate continuously 8KB. Then YOU decide that user shall access these 8KB at linear addr of 900000h. You map 200000h to 900000h, and 300000h to 901000h so that 900000h-901ffffh point to valid location in physical RAM. You don't have to move RAM around just update/change table entries.

How can you then map all "running code" to 0x01000000, and still have diffrent dir pages. ?

not sure where you have problems but you can change Directory table by reloadig CR3 with new physical address (switching tasks). After you have CR3 setup then each entry of Dir table can only point to one address at any given moment. Addresses for different entries may well be different (pointing to different page-table).
Then you can either change Directory entry so that it points to different Page-Table (probably preferred) or change entry in Page-Table.

Sveral different Directory entries can point to different Page-Tables or all Dir entries can point to a single Page-Table.
In both cases you can have different linear addresses pointing to same physical memory.

[kmtdk]

Hi geppy,
well, I learned something from the last posters you send, but it Was as if i needed something,
But i thing i got all now.
Thanks a Lot everyone for helping me though "PAGING"

Kmt

[kmtdk]

Bye the way, i have one last question.
Could you read my "mini tutorial" on paging, and tell me any changes, or someting like that.

The file is a .doc , sry about that.
The link is here: http://www.webmasteren.eu/paging.doc


KMTdk

[JamesM]

Hi,

Apologies for coming in so late after you responded to my last post - I haven't had much time to myself recently to devote to osdev.org.

Okay,,
a describing on: how the 20 bit addressing work, inside the page table, and dir table.
defining a page.
what to do after setting up paging, ( your code, does it location changes ??? or anything else.)
How can you then map all "running code" to 0x01000000, and still have diffrent dir pages. ?

Thanks a Lot

KMT

I fail to see how 20-bit addressing (as you describe it) is the "last" part of paging - rather it seems to me a fairly fundamental part to me, but here goes.

All 4K pages are aligned on 4K boundaries. 4K in hexadecimal is 0x1000, so all page addresses have to be multiples of 0x1000. Put another way, the least significant 12 bits of the address of the start of a page must be zero.

Given that there are 32 bits in an address, 32-12 = 20 bits left. How these bits map to entries in the page tables can be visualised in one of two ways; [assume here that X is the most significant 20 bits of the address of a page.]

- The page directory entry corresponding to the page table to be altered is entry number (X/1024). The page table entry in the selected page table corresponding to the page in question is (X%1024).
OR
- The page directory entry corresponding to the page table to be altered is (X>>10)&0x3FF. The page table entry in the selected page table corresponding to the page in question is (X&0x3FF).

Both ways of thinking obviously come out with the same answer.

Damn! I've got to go. I'll finish this reply later. By the way, I can't read .doc files. Perhaps if you export to a non-retarded format I might be able to peruse it.

[kmtdk]

Well, it is ok
i change the format to a ".txt"
so the link is then http://www.webmasteren.eu/paging.txt
if a pdf is better then it is http://www.webmasteren.eu/paging.pdf

KMTdk