lib0016.html

Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag

</tr>
</table>
<p class="para">Privilege levels are how the operating system prevents user applications from manipulating the kernel image and compromising security. In the real mode discussion, you saw how easy it was to cause havoc and crash the system. I merely waltzed over to the interrupt vector table and erased it. In protected mode, this threat can be dealt with. Vital data structures and operating system code can be safeguarded at the hardware level.</p>
<p class="para">Intel supports four different privilege levels (0&ndash;3). Another way to say this is that Intel supports four <i class="emphasis">rings of protection.</i> These rings are illustrated in <a class="internaljump" href="#ch01fig13">Figure 1.13</a> on the following page. This is actually a pretty simple scheme as far as memory protection is concerned. Decades ago when Control Data was building the NOSVE operating system, the architects wanted to have 15 rings of protection! The odd thing about contemporary operating systems like Linux and Windows is that they only implement two rings of protection (one for the kernel and another for everything else). They don't take full advantage of the facilities offered by the Pentium.</p>
<div class="figure">
<a name="96"></a><a name="ch01fig13"></a><span class="figuremediaobject"><a href="images/fig52%5F01%5F0%2Ejpg" NAME="IMG_13" target="_parent"><img src="images/fig52_01.jpg" height="348" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 1.13</span></span>
</div>
<a name="97"></a><a name="IDX-24"></a>
<p class="para">When a memory location is referenced, the processor performs a series of checks. These checks occur at the same time that the memory address is resolved to its physical location. Because these checks are performed concurrently with the address resolution cycle, there is no performance hit. This is the true beauty of pushing memory management down to the hardware.</p>
<p class="para">If one of the processor's various checks discovers a protection violation, the processor will generate an <i class="emphasis">exception.</i> An exception is a signal produced by the processor. Exceptions are caught and processed using a variation of the processor's interrupt handling features. The exact steps taken are beyond the scope of this discussion. In very general terms, the processor will use special data structures, like the Interrupt Descriptor Table (IDT), to hand off exceptions to the operating system, which can then decide what to do. The operating system is actually responsible for establishing and setting up things like the IDT on behalf of the processor when it bootstraps. This allows the operating system the freedom to register special handlers with the IDT so that the appropriate routines can be invoked when a memory violation occurs.</p>
<p class="para">When a memory exception occurs in Windows, a dialog box will typically appear to announce an access violation and Windows will terminate your program. To see what I mean, compile and run the following program under Windows:</p>
<a name="98"></a><a name="IDX-25"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --overflow.c-- */</span>

<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">int array[4];</span>
    <span style="background-color:d9d9d9">int i;</span>
    <span style="background-color:d9d9d9">for(i=0;i&lt;100;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">array[i]=i;</span>
        <span style="background-color:d9d9d9">printf("set array[%d]=%d\n",i);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">There is a blatant array overflow in the code above. When you run this application, it will crash and Windows will present you with a dialog box like the one shown in <a class="internaljump" href="#ch01fig14">Figure 1.14</a>. If you've never seen a dialog box like this before, take a good look. If you do any sort of pointer-intensive development on Windows, you are bound to see it sooner or later.</p>
<div class="figure">
<a name="99"></a><a name="ch01fig14"></a><span class="figuremediaobject"><a href="images/fig53%5F01%5F0%2Ejpg" NAME="IMG_14" target="_parent"><img src="images/fig53_01.jpg" height="76" width="250" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 1.14</span></span>
</div>
<p class="para">I have not said much about the control registers. The only control register relevant to this current section is the CR0 control register. We'll see a couple of the other control registers in the <a class="internaljump" href="#ch01lev3sec2">next section</a>. The CR0 register's first bit (the lowest-order bit) is known as the PE flag (as in Protected Enable). By setting the PE flag to 1, we switch the processor into protected mode and enable all of the segment protection features discussed earlier. Here is a snippet of assembly code that performs this crucial task:</p>
<div class="informalexample">
<pre class="literallayout">
    MOV EAX,CR0
    OR AL,1
    MOV CR0,EAX
</pre>
</div>
<p class="para">Another equivalent way to do this is to use the special-purpose <span class="fixed">SMSW</span> and <span class="fixed">LMSW</span> system instructions:</p>
<div class="informalexample">
<pre class="literallayout">
    SMSW AX
    OR AL,1
    LMSW AX<a name="100"></a><a name="IDX-26"></a>
</pre>
</div>
<p class="para">You've heard a lot of terms bandied about here: selector, descriptor, etc. If this is your first time reading about protected mode, you may still be confused about what is what. Here is a short summary to help you keep all the cast members of this sitcom organized:</p>
<div class="informaltable">
<table border="0">
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">Cast Member</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">Purpose</p>
</th>
</tr>
<tr>
<td colspan="2">
<hr>
</td>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">Segment selector</p>
</td><td class="td" align="left">
<p class="table-para">Selects a descriptor in a descriptor table</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">Segment descriptor</p>
</td><td class="td" align="left">
<p class="table-para">Describes a memory segment (metadata)</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">Descriptor table</p>
</td><td class="td" align="left">
<p class="table-para">Holds an array of segment descriptors</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">Descriptor table register</p>
</td><td class="td" align="left">
<p class="table-para">Stores the base address of the descriptor table</p>
</td>
</tr>
</tbody>
</table>
</div>
<p class="para">If paging has not been enabled, the final address produced by the scheme in <a class="internaljump" href="#ch01fig09">Figure 1.9</a> is also a physical address, which is to say that it is the same 32-bit value that the processor places on its 32 address lines.</p>
<p class="last-para">If paging is enabled, this is not the case; this leads us to the <a class="internaljump" href="#ch01lev3sec2">next section</a>.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">
<a name="101"></a><a name="ch01lev3sec2"></a>Protected Mode Paging</h4>
<p class="first-para">When paging is enabled, the address resolution scheme in <a class="internaljump" href="#ch01fig09">Figure 1.9</a> becomes a bit more complicated. Take a look at <a class="internaljump" href="#ch01fig15">Figure 1.15</a>. Take a deep breath, and try not to panic.</p>
<div class="figure">
<a name="102"></a><a name="ch01fig15"></a><span class="figuremediaobject"><a href="images/fig54%5F01%5F0%2Ejpg" NAME="IMG_15" target="_parent"><img src="images/fig54_01.jpg" height="252" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 1.15</span></span>
</div>
<a name="103"></a><a name="IDX-27"></a>
<p class="para">Basically, we have taken the address resolution process in <a class="internaljump" href="#ch01fig09">Figure 1.9</a> and appended it with several steps so that we can accommodate all of the extra bookkeeping needed for paging. The address formed by the segment descriptor and the offset address in <a class="internaljump" href="#ch01fig09">Figure 1.9</a> is no longer the address of a byte in physical memory. Instead, a 32-bit quantity is formed that is composed of three distinct offset addresses. Two of these offset addresses are 10 bits in size and the remaining offset address is 12 bits in size.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">I will refer to this three-part, 32-bit quantity as a <i class="emphasis">linear address</i> to help distinguish it from the physical address of a byte in memory. The GDTR register holds the linear address of the base of the GDT data structure. Now you know why I emphasized this distinction earlier.</p>
<p class="last-para">Code that runs in protected mode with paging enabled lives in the alternate reality of linear addresses. Such code deals with "fake" 32-bit addresses that seem real enough to the code. Behind the scenes, the processor resolves fake/linear addresses to addresses that specify actual physical storage.</p>
</td>
</tr>
</table>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">Paging facilities on the Intel platform were first introduced so that the processor could backfill unused areas of system memory (<span class="fixed">0xB0000</span> to <span class="fixed">0xFFFFF</span>) with the <span class="fixed">EMM386.EXE</span> program.</p>
</td>
</tr>
</table>
<p class="para">The last 10 bytes of the linear address are an offset address of an entry in the <i class="emphasis">page directory</i>. The page directory is just an array of 32-bit entries whose base address is stored in the CR3 control register. A page directory's entry contains, among other things, the base address of a <i class="emphasis">page table.</i>
</p>
<p class="para">Given that a page directory entry has referenced the base address of a certain page table, the middle 10 bytes of the linear address serve as an offset address into that page table. This offset address references a 32-bit page table entry. The 32-bit page table entry contains, among other things, the base address of an actual 4KB <i class="emphasis">page</i> of memory.</p>
<p class="para">This is where the first 12 bytes of the linear address come into play. These 12 bytes form an offset address that is added to the base address in the page table entry. The sum of these values forms an actual physical address of a byte in virtual memory. This byte is either in DRAM or has been paged to disk. You might also notice that a 12-bit offset limits the size of the memory page, in this case, to 4,096 bytes (4KB).</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">The base address stored in the page table entry is 20 bits in size. The processor assumes that these are the 20 most significant bits in a 32-bit base address, which is another way to say that the extra 12 bits are implied and all zero.</p>
<a name="104"></a><a name="IDX-28"></a>
<div class="informaltable">
<table border="0">
<tbody>
<tr valign="middle">
<td class="td" align="left">
<p class="table-para">For example, a base address of:</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">0xCAEEB</span>
</p>
</td>
</tr>
<tr valign="middle">
<td class="td" align="left">
<p class="table-para">is really:</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">0xCAFEB [0] [0] [0].</span>
</p>
</td>
</tr>
</tbody>
</table>
</div>
<p class="last-para">This is similar to real mode, where the segment address, expressed in hexadecimal, has a single implied zero at the end. This convention guarantees that the base address of a page always occurs in multiples of 4KB.</p>
</td>
</tr>
</table>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">Most operating systems assign each process their own page directory so that each program's linear address space maps to a different section of physical storage. This guarantees, as long as the page structures entries are not the same, that one process will not be able to access the physical memory of another process.</p>
</td>
</tr>
</table>
<p class="para">If the byte referenced in the page is in physical memory, then we are done. If the byte is not in memory, then a <i class="emphasis">page fault</i> is generated. When this happens, the processor will produce a page fault and hand it off to the local operating system using the exception handling data structures. The operating system is expected to set these data structures up. The operating system, once it has received the fault signal, will then load the page containing this byte into DRAM so that it can be manipulated. Page faults are the backbone of virtual memory on the Intel hardware.</p>
<p class="para">Now you know why your computer's hard drive goes crazy when you have too many applications running. The computer is busy moving programs, or parts of programs, on and off the hard drive. <i class="emphasis">Thrashing</i> occurs when you have so many applications loaded that the computer is too busy managing them and has no time to actually run them.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">For the sake of simplicity (and sanity) I am going to stick to a 4KB paging scheme that uses only 32 address lines. This is shown in <a class="internaljump" href="#ch01fig15">Figure 1.15</a>. Intel has paging schemes where the page size is 4MB or 2MB. However, I don't see much use for a 4MB or 2MB paging scheme. Perhaps these larger paging settings were introduced to help kernels save their own images. There are high-availability operating systems, like EROS, that periodically save an image of the entire operating system. The only thing that would make these two larger paging schemes valuable, in the traditional sense, would be dramatic advances in disk I/O hardware.</p>
</td>
</tr>
</table>
<p class="para">Let's take a closer look at what the page directory and page table entries look like. (See <a class="internaljump" href="#ch01fig16">Figure 1.16</a>.)</p>
<div class="figure">
<a name="105"></a><a name="ch01fig16"></a><span class="figuremediaobject"><a href="images/fig57%5F01%5F0%2Ejpg" NAME="IMG_16" target="_parent"><img src="images/fig57_01.jpg" height="204" width="310" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 1.16</span></span>
</div>
<p class="para">A page directory entry has a number of special-purpose flags related to caching that I am not going to go into. The really important fields of the entry are the base address of the page table and the page size (PS) flag. The present flag (P) is maintained by the local operating system and is used to indicate if the page table is present in memory. If it is not, the page table will need to be loaded via a <a name="106"></a><a name="IDX-29"></a>page fault so that the address resolution cycle can continue. Most operating systems, however, are wise enough to leave their crucial data structures in memory.</p>
<p class="para">The layout of a page table entry is displayed in <a class="internaljump" href="#ch01fig17">Figure 1.17</a>. As you can see, it is very similar to the setup of the page directory entry. The difference is that the fields in a page directory entry are concerned with a page table. The fields in the page table entry are concerned with a 4KB page of memory.</p>
<div class="figure">
<a name="107"></a><a name="ch01fig17"></a><span class="figuremediaobject"><a href="images/fig57%5F02%5F0%2Ejpg" NAME="IMG_17" target="_parent"><img src="images/fig57_02.jpg" height="235" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 1.17</span></span>
</div>
<a name="108"></a><a name="IDX-30"></a>
<p class="para">One new thing you might notice is the <i class="emphasis">dirty bit.</i> The dirty bit indicates that the page being r