Operating Systems Development Series

Operating Systems Development - Paging and Virtual Memory
by Mike, 2008

This series is intended to demonstrate and teach operating system development from the ground up.

Introduction

Welcome! :)

In the last tutorial we have finally covered hardware interrupts, implimenting interfaces for the PIC and PIT, set up exception handlers, and more. We have even re-enabled hardware interrupts! Yey!

In this tutorial, we will be going over an even more complex topic: Paging. We cannot go much further without proper memory management. Because of this, I want to cover memory management in a deeper way. It is one of the most fundemental aspects of any computer system, and properly managing memory is important.

So... Are you ready to enter the world of 32 bit virtualization? In this tutorial, We will cover:

Physical Memory
Virtual Memory
Memory Management Unit (MMU)
PAE and PSE
Paging Methods
Pages and Page Faults
The Page Table
The Page Directory Table
Implimenting Paging

Lets get started then!

Memory: A deeper look

Rather then jumping directly into virtual memory and paging, I want to take a different approch here. That is, How can we even understand what virtual memory is without even understanding what memory itself is?

With this, we cannot even begin discussing paging without knowledge of what virtual memory actually is. Because of this, we will first look at what physical memory is first. You know... Those little RAM chips inside of your computer? After looking at physical memory and how it works, we will then take a look at virtual memory, cool?

Here we go...!

Physical Memory

Physical Memory: Abstract

Physical Memory is an abstract block of memory stored within the computers Random Access Memory (RAM). The way physical memory is "stored" within the RAM depends on the type of RAM the system uses. For example, Dynamic Random Access Memory (DRAM) stores each bit of data in its own capacitor that must be refreshed periodically. A capacitor is an electronic device that stores a current for a limited time. This allows it to either store a current (a binary 1), or no current (a binary 0). This is how DRAM chips store individual bits of data in a computer.

Most of the time, the memory types (RAM, SRAM, DRAM, etc.) require a specific type of Memory Controller to interface with the processor and System Bus.

The Memory Controller provides a way of reading and writing memory locations through software. The Memory Controller is also responsible for the constant refreshing of the RAM chips to insure they retain their information.

Memory Controllers contain Multiplexer and Demultiplexer circuits to select the exact RAM chip, and location that refrences the address in the Address Bus. This allows the processor to refrence a specific memory location by sending the memory address through the address bus.

...This is where the software come in, as they tell the processor what memory address to read :)

The Memory Controller selects the location within the RAM chip in a sequence manner. This means, if we access a physical memory location greater then the total amount of memory in the system, it will "wrap around" back to address 0. While this might seem good (Which it is in some ways), it isn't in other ways. For example, we could think we are writing to some location in memory, but--as it does not exist, we can be writing to a different area of memory.

It is possible for memory holes to appear in the Physical Address Space. This can happen if, for example, a RAM chip is in slots 1 and 3, with no RAM chip in slot 2. This means that there is an area of memory between the last byte stored in the RAM at slot 1 and the first byte-1 in slot 3 that does not exist. Reading or writing to these locations have almost the same effect when reading or writing beyond memory. As memory is sequencal, reading or writing to a memory hole with have the effect of reading or writing to the next avilable memory block. This means, we run into the same problem form before: we can be reading or writing to a different location then what we expect.

Because of this, it is important to get all of the information from the BIOS as you can, and never directly probe memory.

Well, Thats all for what physical memory really is. Knowing how memory stores each bit you can probably start seeing where the bytes, words, dword, qwords, tbytes, etc.. start to come in. The most important of these are the byte, as that is the smallest data that the processor can access. But how does the processor know where a byte is located in memory? This is where the Physical Address Space comes in. Lets take a look :)

Physical Address Space (PAS)

This is the address space used by the processor (and translated by the memory controller) to refer to an 8 bit peice of data (ie, a byte) stored in physical memory (RAM). A Memory Address is just a number selected by the Memory Controller for a byte of data. For example, memory address 0 can refer to the first 8 bits of physical memory, memory address 1 can refer to the next 8 bits, and so on. The Physical Address Space is the array of these memory addresses and the actual memory that the memory addresses refer to.

The physical address space is accessed by the processor through the systems address bus (Remember this from Chapter 7?)

Okay, so lessee... the processor now can use an address to refer to a byte of memory. It useually starts from address 0, and increments for each byte in memory. Thats as simple as it can get! But, it still doesnt describe how the software can access memory. Sure, the processor itself now has a way of refrencing memory, but the software does not. The processor, depending on its needs, need to provide specific ways for software to provide software a way to refrence memory. Wait, what? Thats right... different ways of addressing and accessing memory...

Addressing Modes

The Addressing Mode is an abstraction made by the processor to manage how the software accesses the Physical Address Space. This useually allows the software to set up the processors' registers so the processor knows how to refrence memory. We have already seen two: segment:offset memory addressing and descriptor:offset memory addressing.

This is the interface given by the processor for the software to allow a way to access memory.

We have covered the segment:offset addressing mode in Chapter 4 and the descriptor:offset memory addressing mode in Chapter 8.

How Memory Works: Detail

Okay, now lets look at memory in a new way. We have already covered alot of details on what memory is, address space and addressing modes. Now, lets put everything together, shall we?

Alot of the information in this section is not needed, but I decided to include it for completness sake. Don't worry to much if you do not understand everything here.

In Chapter 7, we have looked at a basic overview of a computer system and system architecture. We have talked about how the processor's system bus connects to the memory controller which is used to provide the system a way to control physical RAM. Kind of like this:

Thats it! This is how the physical RAM connects and communicates with the rest of the system. In the above image, the DDR Controller is the memory controller. The Translation Lookaside Buffer (TLB) sits between the memory controller and processor. With this, the system bus connects all three of them through its address bus, data bus and control bus. The only 2 lines from the control bus that are important to us right now are the RW line and CLK line.

The TLB is only used when paging is enabled. Because of this, we will look at it a little more later.

Okay, so what actually happens when we write data to a physical memory location? During a write operation, the processor sets the RW pin to high (a logical 1). This tells the devices it connects to that a write operation is to take place. The processor resets the IO Control line to low (a logical 0). This insures the IO SubSystem ignores the command (Meaning its not an IN/OUT port instruction), but rather for the memory controller. The processor then copies the address to write to onto the address bus and the data to write onto the data bus. Because these lines are connected indirectly to the memory controller, the memory controller is able to see it is a write operation. So, all the memory controller needs to do is translate the memory address on the address bus using its demultiplexer circuit to find the RAM chip to use, and linear offset byte into the RAM chips memory space. The memory controller then copies the data from the data bus to this location, and refreshes the memory state on the next clock signal.

During a read operation it follows almost the same process as a write operation. Except, the RW line is set low to indicate a read operation. Also, the memory controller, after translating the memory address into an offset into the RAM chip, copies the data stored in that location and places it on the data bus for the processor. The memory controller then refreshes the memory state on the next clock signal.

The CLK signal is used to synchronize the exchange of addresses and data values through the reads and writes. Communication with the memory chip is started when the CLK line is a logical 1 (set high). During this period that the CLK line is held high the address is placed on the address lines and the R/W line is either taken high for a write or low for a read.

During execution the processor will constantly be flipping the clock line high and low in order to perform reads and writes with the memory controller.

While paging is disabled, the TLB itself does nothing at all. Notice that the TLB is not used at all when reading or writing memory.

The Need for Virtualization

There are alot of big problems with directly accessing and using physical memory that you may already know (or even have experience with yourself ;) ) One that we have just seen was when we would access to a block of memory that does not exist. Knowing that both programs and data are in memory, it is also possible for programs to access each others memory spaces, or even corropt and overwrite themselves or other programs without knowing it. After all, there is no memory protection.

Also, it is not always possible to load a file or program into a sequencial area of memory. This is when fragmentation happens. For an example, lets say we have 2 programs loaded. One at 0x0, the other at 0x900. Both of these programs requested to load files, so we load the data files:

Notice what is happening here. There is alot of unused memory between all of these programs and files. Okay...What happens if we add a bigger file that is unable to fit in the above? This is when big problems arise with the current scheme. We cannot directly manipulate memory in any specific way, as it will currupt the currently executing programs and loaded files.

Then there is the problems of where each program is loaded at. Each program will be required to be Position Indipendent or provide relocation Tables. Without this, we will not know what base address the program is supposed to be loaded at.

This adds on two new problems. How do we know where to load a program at? Coinsidering all we have is a binary image, we cannot know. However, if we make it standard that all programs begin at the same address--lets say, 0x0, then we can know. This would work--but is impossible to impliment if we plan to support multitasking. However, if we give each program there own memory space, that virtually begins at 0x0, this will work. After all, from each programs' perspective, they are all loaded at the same base address--even if they are different in the real (physical) memory.

What we need is a way to abstract physical memory in such a way that we do not need to worry about these details anymore. I am sure by now you can see the problems with working with pysical memory by now. This is where virtualization comes in...Lets take a look!

Virtual Memory

In order to better understand how virtual memory works, we should first have a better understanding of what virtual memory is.

As you know, when we are not using paging, all of the addresses that we use to refrence physical memory are sent directly from the processor across the systems address bus to the memory controller. What does this mean? Anytime we refrence a memory location, the memory address is unmodified; it means we will refrence that exact location within the physical address space (PAS).

In a system that supports "virtual addressing", things are a little different. On the x86 architecture, All memory addresses go through a Translation Lookaside Buffer (TLB) that sits between the memory controller and the processor. You have seen this before, remember? We will look at the TLB closer a little later, dont worry ;)

Virtual Memory: Abstract

Virtual Memory is a special Memory Addressing Scheme implimented by both the hardware and software. It allows non contigous physical memory to act as if it was contigius memory.

Okay... So what exactally does this mean? This parts a little tricky. While a physical address is restricted to physical memory, a virtual address is not. This is an important concept. It allows a virtual address to be much larger then the amount of physical memory on the system. It also allows us to manage this much larger Virtual Address Space in a new way (as you will see very soon).

Virtual Address Space (VAS)

A Virtual Address Space is a Program's Address Space. One needs to take note that this does not have to do with Physical Memory. The idea is so that each program has their own independent address space. This insures one program cannot access another program, because they are using a different address space.

Because VAS is Virtual and not directly used with the physical memory, it allows the use of other sources, such as disk drives, as if it was memory. That is, It allows us to use more "memory" then what is physically installed in the system.

This fixes the "Not enough memory" problem.

Also, as each program uses its own VAS, we can have each program always begin at base 0x0000:0000. This solves the relocation problems discussed ealier, as well as memory fragmentation--as we no longer need to worry about allocating continous physical blocks of memory for each program.

Virtual Addresses are mapped by the Kernel trough the MMU. More on this a little later.

Memory Management Unit (MMU)

The Memory Management Unit (MMU) (Also known as Paged Memory Management Unit (PMMU)) sets between (Or as part of) the microprocessor and the memory controller. While the memory controller's primary function is the translation of memory addresses into a physical memory location, the MMU's purpose is the translation of virtual memory addresses into a memory address for use by the memory controller.

This means--when paging is enabled, all of our memory refrences go through the MMU first!

MMU Virtual Addressing

This is important! We will be revisting this a little later so do not worry if you do not understand this yet. :)

A virtual address is a 32 bit address that follows the format (shown in binary form):

AAAAAAAAAA         BBBBBBBBBB        CCCCCCCCCCCC
directory index    page table index  offset into page

Okay, okay, alot of this might seem confusing right now. Don't worry--everything will be explained a little later I promise :)

For a little example, the virtual address 0xc0000000 will be the 768th directory index. the MMU will look at what physical address this translates to by looking at the 768 directory entry that we have set up. Once again, if you are a little lost dont worry--Alot of the info here will make alot more sense later on.

For speed purposes, if the system suppots a TLB, the virtual address is first looked up in the TLB. If the MMU finds the page in the TLB (A TBL hit), the physical frame address is retrieved from the page. If there is no match, the MMU is required to look up the physical frame address from the page table. This is how the MMU retrives the physical address form the virtual address.

If the hardware is unable to find the page, the physical address is invalid, or the page is not in physical memory, the MMU signals the processor to generate a page fault exception.

Translation lookaside buffer (TLB)

This is a cache stored within the processor used to improve the speed of virtual address translation. It is useually a type of Content-addressable memory (CAM) where the search key is the virtual address to translate, and the result is the physical frame address. If the address is not in the TLB (A TLB miss), the MMU searches through the page table to find it. If it is found in the TLB, it is a TLB Hit. If the page is not found or invalid inside of the page table during a TLB miss, the processor will raise a Page Fault exception for us.

Think of a TLB as a table of pages stored in a cache instead of in RAM--as that is basically what it is.

This is important! The pages are stored in page tables. We set up these page tables to describe how physical addresses translate to virtual addresses. In other words: The TLB translates virtual addresses into physical addresses using the page tables *we* set up for it to use! Yes, thats right--we set up what virtual addresses map to what. We will look at how to do this a little later, cool? Dont worry--its not that bad ;)

Segmented Virtual Memory

*edited out for incorrect content. We will re-add this section on the upcoming revision of this article. Dont worry too much--we arn't using this method. -Mike

Paged Virtual Memory

Virtual Memory also provides a way to indirectly use more memory then we actually have within the system. One common way of approching this is by using Page files, stored on a hard drive or a swap partition.

Virtual Memory needs to be mapped through a hardware device controller in order to work, as it is handled at the hardware level. This is normally done through the MMU, which we will look at later.

For an example of seeing virtual memory in use, lets look at it in action:

Notice what is going on here. Each memory block within the Virtual Addresses are linear. Each Memory Block is mapped to either it's location within the real physical RAM, or another device, such as a hard disk. The blocks are swapped between these devices as an as needed bases. This might seem slow, but it is very fast thanks to the MMU.

Remember: Each program will have its own Virtual Address Space--shown above. Because each address space is linear, and begins from 0x0000:00000, this immiedately fixes alot of the problems relating to memory fragmentation and program relocation issues.

Also, because Virtual Memory uses different devices in using memory blocks, it can easily manage more then the amount of memory within the system. i.e., If there is no more system memory, we can allocate blocks on the hard drive instead. If we run out of memory, we can either increase this page file on an as needed bases, or display a warning/error message,

Each memory "Block" is known as a Page, which is useually 4096 bytes in size. We will cover Pages a little later.

Okay, so a Page is a memory block. This memory block can either be mapped to a location in memory, or to another device location, such as a hard disk. This is an unmapped page. If software accessed an unmapped page (The page is not currently in memory), it needs to be loaded somehow. This is done by our Page fault handler.

We will cover everything later, so do not worry if this sounds hard :)

Because we are talking about paging in general, I think now would be a good idea to look at some extensions that may be used with paging. Lets have a look!

PAE and PSE

Physical Address Extension (PAE)

PAE is a feature in x86 microprocessors that allows 32 bit systems to access up to 64 GB of physical memory. PAE supported motherboards use a 36 line address bus to achieve this. Paging support with PAE enabled (Bit 5 in the cr4 register) is a little different then what we looked at so far. I might decide to cover this a little later, however to keep this tutorial from getting even more complex, we will not look at it now. However, I do encourage readers to look into it if you are interested. ;)

Page Size Extension (PSE)

PSE is a feature in x86 microprocessors that allows pages more then 4KB in size. This allows the x86 architecture to support 4MB page sizes (Also called "huge pages" or "large pages") along side 4KB pages.

The World of Paging

Let the madness begin :)

Introduction

Woo-hoo! Welcome to the wonderful and twisted-minded world of paging! With all of the fundemental concepts that we have went over already, you should have a nice and good grasp at what paging and virtual memory is all about. This is a great start, don't you think?

Okay, cool...but, how do we actually impliment it? How does paging work on the x86 architecture? Lets take a look!

Pages

A Page (Also known as a memory page or virtual page) is a fixed-length block of memory. This block of memory can reside in physical memory. Think of it like this: A page describes a memory block, and where it is located at. This allows us to "map" or "find" the location of where that memory block is at. We will look at mapping pages and how to impliment paging a little later :)

The i86 architecture uses a specific format for just this. It allows us to keep track of a single page, and where it is currently located at. Lets take a look..

Page Entry Format

The x86 architecture uses a specific format for page entries stored within a programs virtual address space. This allows us to test different properties of the pages, or to get their frame address in physical memory. Lets take a look...

Bit 0 (P): Present flag

0: Page is not in memory
1: Page is present (in memory)

Bit 1 (R/W): Read/Write flag

0: Page is read only
1: Page is writable

Bit 2 (U/S):User mode/Supervisor mode flag

0: Page is kernel (supervisor) mode
1: Page is user mode. Cannot read or write supervisor pages

Bits 3-4 (RSVD): Reserved by Intel
Bit 5 (A): Access flag. Set by processor

0: Page has not been accessed
1: Page has been accessed

Bit 6 (D): Dirty flag. Set by processor

0: Page has not been written to
1: Page has been written to

Bits 7-8 (RSVD): Reserved
Bits 9-11 (AVAIL): Available for use
Bits 12-31 (FRAME): Frame address

Colldos! Thats all? Well.. I never said it was hard ;)

Quite possibly the most important thing here is the frame address. The frame address represents the 4KB physical memory location that the page manages. This is vital to know when understanding paging, however it is hard to describe why it is so right now. For now, just remember that each and every page manages a block of memory. If the page is present, it manages a 4KB physical address space in physical memory.

The Dirty Flag and Access Flag are set by the processor, not software. You might wonder on how the processor knows what bits to set; ie, where they are located in memory. We will look at that a little later. Just rememeber that, this will allow the software or executive to test if a page has been accessed or not.

The present flag is an important one. This one single bit is used to determin if a page is currently in physical memory or not. If it is currently in physical memory, the frame address is the 32 bit linear address for where it is located at. If it is not in physical memory, the page must reside on another location--such as a hard disk.

If the present flag is not set, the processor will ignore the rest of the bits in the structure. This allows us to use the rest of the bits for whatever purpose...perhaps where the page is located at on disk? This will allow--when our page fault handler gets called--for us to locate the page on disk and swap the page into memory when needed.

Lets give out a simple example. Lets say that we want this page to manage the 4KB address space beginning at physical location 1MB (0x100000). What this means--to put in other words--is that this page is "mapped" to address 1MB.

Lets take a look at creating this page:

%define		PRIV		3

mov		ebx, 0x100000 | PRIV	; this page is mapped to 1MB

Notice that 0x100000 is 4KB aligned? It ORs it with 3 (11 binary which sets the first two bits. Looking at the above table, we can see that it sets the present and read/write flags, making this page present (Meaning its in physical memory. This is true as it is mapped from physical address 0x100000), and is writable.

Thats it! You will see this example expand further in the next few sections so that you can start seeing how everything fits in, so don't worry to much if you still do not understand.

Okay, this is great as this setup allows us to keep track of a single page. However, it is useless by itself as a typical system will need to have alot of pages. This is where a page table comes in.

The Page Table

The page table...hm...where oh where did we hear that term before? *looks one line up*. Oh, right ;)

A Page Table is..well..a table of pages. (Surprised?) A page table allows us to keep track of how the pages are mapped between physical and virtual addresses. Each page entry in this table follows the format shown in the previous section.

While it is a very simple structure, it has a very important purpose. The page table containes a list of all the pages it containes, and how they are mapped. By "mapping", We refer to how the virtual address "maps" to the physical frame address. The page table also manages the pages, weather they are present, how they are stored, or even what process they belong to (This can be set by using the AVAIL bits of a page. This may not be needed, it depends on the implimentation of the system.)

Lets stop for a moment. Remember that a page manages 4KB of physical address space? By itself, a page is nothing more then a data structure that describes the properties of a specific 4KB region of physical memory. Because each page "manages" 4KB of physical memory, putting 1024 pages together we have 1024*4KB=4MB of managed virtual memory. Lets take a look at how its set up:

Thats an example of a page table. Notice how it is nothing more then an array 1024 page entries. Knowing that each page manages 4KB of physical memory, we can actually turn this little table into its own virtual address space. How can we do this? Simple: By deciding the format of a virtual address.

Heres an example: Lets say we have designed a new virtual address format like this:

AAAAAAAAAA        BBBBBBBBBBBB
page table index  offset into page

This is our format for a virtual address. So, when paging is enabled, all memory addresses will now follow the above format. For example, lets say we have the following instruction:

mov	ecx, [0xc0000]

Here, 0xc0000 will be treated like a virtual address. Lets break it apart:

  11000000        000000000000	; 0xc0000 in binary form
AAAAAAAAAA        BBBBBBBBBBBB
page table index  offset into page

What we are now doing is an example of address translating. We are actually translating this virtual address to see what physical location it refers to. The page table index, 11000000b = 192. This is the page entry inside of our page table. We can now get the base physical address of the 4KB that this page manages. If this page is present (Pages present flag is set), all we need to do is access the pages frame address to access the memory. If this page is NOT present, then generate a page fault--The page data might be somewhere on disk. The page fault handler will allow us to copy the 4KB data for the page into memory somewhere and set the page to present and update its frame address to point to this new 4KB block of physical memory.

Okay okay, I know. This little example of creating a fake "virtual address" might seem silly, but guess what? This is how its actually done! The actual format of a virtual address is a little bit more complex in that there are three sections instead of 2. However, if we omit the first section it would be exactally the same as our above example.

I hope by now you are starting to see how everything fits together, and the importance of page tables.

There are several different ways to impliment page tables. Okay, We can easily just use an array of pages, but there are alot of problems with this method. First: How do we know what pages belong where? What should we look for when searching for a page? How should we search for a page? How should we allocate a page table? Per process? Right about now you can probably see both the importance of page tables, and why they are important.

Inverted Page Table (IPT)

*To be added*

Multilevel Page Table

*To be added*

Virtualized Page Table

*To be added*

Page Size

A system with smaller page sizes will require more pages then a system with larger page sizes. Because the table keeps track of all pages, a system with smaller page sizes will also require a larger page table because there are more pages to keep track of. Simple enough, huh?

The i86 architecture supports 4MB (2MB pages if using Page Address Extension (PAE)) and 4KB sized pages.

The important things to note are: Notice how page size may effect the size of page tables.

Page Directory Table

Okay... We are almost done! A page table is a very powerful structure as you have seen. Remember our previous virtual address example? e gave an example of a virtual addressing system where each virtual address was composed of two parts: A page table entry and a offset into that page.

On the x86 architecture, the virtual address format actually uses three sections instead of two: The entry number in a page directory table, the page table index, and the offset into that page.

A Page Directory Table is nothing more then an array of Page Directory Entries. I know I know... How useless and non-informative was that last sentence? ;)

So, anyways, lets first look at a page directory entry. Then we will start looking at the directory table, and where it all fits in...

Page Directory Entry Format

The format of an entry in the page directory table is very close to that of the page entry format we looked at above. Because of this, they are pretty much interchangable, but their are some minor differences.

Bit 0 (P): Present flag

0: Page is not in memory
1: Page is present (in memory)

Bit 1 (R/W): Read/Write flag

0: Page is read only
1: Page is writable

Bit 2 (U/S):User mode/Supervisor mode flag

0: Page is kernel (supervisor) mode
1: Page is user mode. Cannot read or write supervisor pages

Bit 3 (PWT):Write-through flag

0: Write back caching is enabled
1: Write through caching is enabled

Bit 4 (PCD):Cache disabled

0: Page table will not be cached
1: Page table will be cached

Bit 5 (A): Access flag. Set by processor

0: Page has not been accessed
1: Page has been accessed

Bit 6 (D): Reserved by Intel
Bit 7 (PS): Page Size

0: 4 KB pages
1: 4 MB pages

Bit 8 (G): Global Page (Ignored)
Bits 9-11 (AVAIL): Available for use
Bits 12-31 (FRAME): Page Table Base address

Understanding the Page Directory Table

The Page Directory Table is sort of like an array of 1024 page tables. Remember that each page table manages 4MB of a virtual address space? Well... Putting 1024 page tables together we can manage a full 4GB of virtual addresses. Sweet, huh?

Okay, its a little more complex then that, but not that much. The Page Directory Table is actually an array of 1024 page directory entries that follow the format above. Look back at the format of an entry and notice the Page Table Base address bits. This is the address of the page table this directory entry manages.

It may be easier to see it visually, so here you go:

Notice what is happening here. Each page directory entry points to a page table. Remember that each page manages 4KB of physical (and hence virtual) memory? Also, remember that a page table is nothing more then an array of 1024 pages? 1024*4KB = 4MB. This means that each page table manages its own 4MB of address space.

Each page directory entry provides us a way to manage each page table much easier. Because the complete page directory table is an array of 1024 directory entries, and that each entry manages its own table, we effectivly have 1024 page tables. From our previous calculation we know each page table manages 4MB of address space. So 1024 page tables*4MB size= 4GB of virtual address space.

I guess thats it for ... believe it or not... everything. See, its not that hard, is it? In the next section, we will be revisiting the real format of an x86 virtual address, and you will get to see how everything works together!

Understanding Paging

Note: All of the example code here is also inside of paging.inc inside of our bootloader inside of this tutorials' demo. Check it out!

We are almost done!! I feel this chapter is already big enough, dont you? We have covered almost every aspect of paging, its components, virtual memory, and even physical memory! However, we still have not covered the most important part of paging: Implimenting it, and understanding paging itself and how it works. Lets look at that next!

Putting everything together: How it works

I am to admit: There is alot of stuff in this chapter. I wanted to cover everything in this chapter, but still try to keep things understandable without getting to complex.

Everything we have covered is completely useuless by themselves. We have not looked at how everything comes together yet. This is where everything starts to come together, and where I hope things start becoming clear.

Virtual Addressing and Mapping Addresses

When we enable paging, all memory refrences will be treated as a virtual address. Remember the format of a virtual address? This is the format of a x86 virtual address:

AAAAAAAAAA         BBBBBBBBBB        CCCCCCCCCCCC
directory index    page table index  offset into page

This is very important! This tells the processor (And *us*) alot of information.

The directory index portion tells us what index into the current page directory to look in. Look back up to the Directory Entry Structure format in the previous section. Notice that each directory table entry containes a pointer to a page table. You can also see this within the image again in that section.

Because each index within the directory table points to a page table, this tells us what page table we are accessing.

The page table index portion tells us what page entry within this page table we are accessing.

...And remember that each page entry manages a full 4KB of physical address space? The offset into page portion tells us what byte within this pages physical address space we are refrencing.

Notice what happened here. We have just translated a virtual address into a physical address using our page tables. Yes, its that easy. No trickery involved.

Lets look at another example. Lets assumed that virtual address 0xC0000000 was mapped to physical address 0x100000. How do we do this? We need to find the page in our structures that 0xC0000000 refer to -- just like we did above. In this case 0xC0000000 is the virtual address, so lets look at its format:

1100000000         0000000000        000000000000		; 0xC0000000 in binary form

AAAAAAAAAA         BBBBBBBBBB        CCCCCCCCCCCC
directory index    page table index  offset into page

Remember that the directory index tells us what page table we are accessing within the page directory table? So... 1100000000b (The directory index) = 768th page table.

Remember that the page table index is the page we are accessing within this page table? That is 0, so its the first page. Also note the offset byte in this page is 0.

Now, all we need to do is set the frame address of the first page in the 768th page table to 0x100000 and voila! You have just mapped 3GB virtual address to 1MB physical! Knowing that each page is 4KB aligned, we can keep doing this in increments of 4KB physical addresses.

Here is a full example that maps the 3GB virtual address page table to 1MB physical address space. Notice how it works:

; page directory table
%define		PAGE_DIR		0x9C000

; 768th page table. Address must be 4KB aligned
%define		PAGE_TABLE_768		0x9E000

;------------------------------------------
; set up the entries in the directory table
;------------------------------------------

mov		eax, PAGE_TABLE_768 | 3		; set directory entry: Points to table with its present;writable bits set
mov		dword [PAGE_DIR+(768*4)], eax	; place the entry into the 768th index of directory table. This is what
						; tells the cpu this is the 768th table

; install the directory table by simply putting PAGE_DIR into cr3!

;------------------------------------------
; map the 768th table to physical addr 1MB
; the 768th table starts the 3gb virtual address space
;------------------------------------------
 
mov		eax, PAGE_TABLE_768		; page table location
mov		ebx, 0x100000 | 3		; starting physical address of page (1MB); sets page entries flags
mov		ecx, 1024			; for every page in table...
.loop:
mov		dword [eax], ebx		; write the entry in page table
add		eax, 4				; go to next page entry in table (Each entry is 4 bytes)
add		ebx, 4096			; go to next page address (Each page is 4Kb)
loop	.loop					; go to next entry

Thats all!?? Yep, pretty much. As soon as paging is enabled, accessing address 0xC0000000 will now be accessing physical address 0x100000 thanks to our code.

Identity Mapping

Identity Mapping is nothing more then mapping a virtual address to the same physical address. For example, virtual address 0x100000 is mapped to physical address 0x100000. Yep--Thats all there is to it. The only real time this is required is when first setting up paging. It helps insure the memory addresses of your current running code of where they are at stays the same when paging is enabled. Not doing this will result in immediate triple fault.

Here is an example. PAGE_TABLE_0 is the first page table. This is entry 0 of the directory table. Assuming that our code is located at 0x500, we will want to idenitity map the first page table before enabling paging. Knowing that there are 1024 pages in a page table, all we need to do is write 1024 pages in the table beginning with physical address 0, and, for each page, increment the physical address by 4096 bytes (Which is 4KB - Remember that each page handles 4KB of memory?)

; 0th page table. Address must be 4KB aligned
; Entry 0 in page directory table must point here as it is the first page table
%define		PAGE_TABLE_0		0x9D000

	;------------------------------------------
	;	idenitity map 1st page table (4MB)
	;------------------------------------------

	mov		eax, PAGE_TABLE_0				; first page table
	mov		ebx, 0x0 | 3					; starting physical address of page
	mov		ecx, 1024					; for every page in table...
.loop:
	mov		dword [eax], ebx				; write the entry
	add		eax, 4						; go to next page entry in table (Each entry is 4 bytes)
	add		ebx, 4096					; go to next page address (Each page is 4Kb)
	loop	.loop							; go to next entry

Thats all there is to it... ;) Now that we have idenitity mapped our address space it is now safe to enable paging. Lets take a look...!!

Enabling Paging

Once you have identity mapped your current running area of memory, all that is left to do is to load your current page directory into the processors CR3 register. Afterwords, simply set the PG bit in the CR0 control register and thats all! :)

For example:

	;------------------------------------------
	;	install directory table
	;------------------------------------------

	mov		eax, PAGE_DIR
	mov		cr3, eax

	;------------------------------------------
	;	enable paging
	;------------------------------------------

	mov		eax, cr0
	or		eax, 0x80000000
	mov		cr0, eax

Thats all that is needed and paging is now enabled!

Paging: Methods

*I plan on adding to this section*

Demand Paging

Loader Paging

Anticipatory Paging

Swap Prefetch

Precleaning

Page Faults

If a virtual address is refrencing a directory entry or page that is marked not present, the processor generates a #PG exception (exception 14). It will also generate this exception if a process running in a user mode tries to write to a page marked read-only or any kernel-only page. The processor also raises this exception if any reserved bits are set in the page directory entry or page entry structures.

In our current kernel, this means when a page fault is generated, the processor will invoke our page_fault() C++ exception handler. Remember from Chapter 15 that then processor also pushes an error code for us on this exception?

Thanks to the way our HAL directly installs these interrupt handlers (Please see the HAL's setvect() routine), the processor calls our exception handler as-is:

//! page fault
void interrupt _cdecl page_fault (unsigned int cs,unsigned int err, unsigned int eip, unsigned int eflags) {

	intstart ();
	kernel_panic ("Page Fault");
	for (;;);
}

The pushed error code is stored in err. The error code has the following format:

Bit 0: Page present

0: The #PF was generated because the page was not present
1: The page was present, the #PF was not because of this

Bit 1: Operation

0: This was a read operation on the page
1: this was a write operation on the page

Bit 2: Mode

0: The processor was running in kernel mode (ring 0) when #PF fired
1: the processor was running in user mode (ring 3) when #PF fired

Bit 3: Reserved

0: Reserved bits were not written to; #PF was not caused by this
1: Reserved bits were overwritten. #PF was generated because of this

Bit 4: Instruction Fetch

0: #PF did not occur durring an instruction prefetch
1: #PF occurred during an instruction prefetch

As you can see, the processor gives us alot of information for us to find out what caused the page fault and try to correct the problem.

The processor also saves the virtual address that caused the page fault into the CR2 register. This will allow you to find the page in our page directory structures that it is failing on.

With this, as with all other exceptions, the processor also pushes the cs:eip that caused the exception on the stack so we can even find the process that has caused this to happen.

As you can see, we have alot of information to resolve the problem. And hey, if it cannot be resolved, we can always just terminate the current process ;) Your users might not be too happy about it though :)

There isn't that much that we can do in the early stages of an operating system, so all we do is print our some error information and halt the system.

Putting it Together: Demo

*Demo coming soon! We will also be describing the C++ paging interface code within the demo here*

Conclusion

I am very glad to get this one done! We have covered alot of information and ground in this tutorial: Physical memory, Virtual Memory, Virtual addressing and translation, paging, methods, and more. With this tutorial, we are not out of the paging word yet! However, we can all saftely go to bed tonight knowing that we have a better understanding of it, how it works, and hot to work with it. See? Its not so bad :)

Now that we have paging started, we can start diving into that of memory and heap management. We will be going back to the kernel itself again and impliment a basic heap manager for our kernel. This is just one of those things nobody likes doing, but is required. Don't worry, we will get back to the fun stuff soon enough :) Its not too bad though--Having a heap manager will greatly simplify some of the more complex tasks that lie ahead. I'll see you there ;)

Until next time,

~Mike ();
BrokenThorn Entertainment. Currently developing EvolutionEngine and MicroOS Operating System.

Questions or comments? Feel free to Contact me.