lib0022.html

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

</td><td class="td" align="left">
<p class="table-para">4KB units</p>
</td><td class="td" align="left">
<p class="table-para">4KB units</p>
</td><td class="td" align="left">
<p class="table-para">4KB units</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">32-bit code/data</b>
</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Present in</b> <b class="bold">memory</b>
</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td><td class="td" align="left">
<p class="table-para">Yes</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Privilege</b>
</p>
</td><td class="td" align="left">
<p class="table-para">0x0</p>
</td><td class="td" align="left">
<p class="table-para">0x0</p>
</td><td class="td" align="left">
<p class="table-para">0x3</p>
</td><td class="td" align="left">
<p class="table-para">0x3</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Type</b>
</p>
</td><td class="td" align="left">
<p class="table-para">Execute/Read</p>
</td><td class="td" align="left">
<p class="table-para">Read/Write</p>
</td><td class="td" align="left">
<p class="table-para">Execute/Read</p>
</td><td class="td" align="left">
<p class="table-para">Read/Write</p>
</td>
</tr>
</tbody>
</table>
<p class="para">The segment selectors corresponding to these descriptors are displayed in <a class="internaljump" href="#ch02fig07">Figure 2.7</a>.</p>
<div class="figure">
<a name="184"></a><a name="ch02fig07"></a><span class="figuremediaobject"><a href="images/fig98%5F01%5F0%2Ejpg" NAME="IMG_29" target="_parent"><img src="images/fig98_01.jpg" height="88" width="253" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.7</span></span>
</div>
<p class="para">There are 12 descriptors defined in the source code snippet. Four are not used and four are dedicated to advanced power management (APM). The GDT, however, is not guaranteed to be a fixed size. As <a name="185"></a><a name="IDX-71"></a>of kernel version 2.4, every CPU on the motherboard gets two segment descriptors in the GDT. Each CPU gets a descriptor specifying a Task State Segment (TSS) and a descriptor specifying a segment that stores a Local Descriptor Table (LDT). This is illustrated in <a class="internaljump" href="#ch02fig08">Figure 2.8</a>.</p>
<div class="figure">
<a name="186"></a><a name="ch02fig08"></a><span class="figuremediaobject"><a href="images/fig99%5F01%5F0%2Ejpg" NAME="IMG_30" target="_parent"><img src="images/fig99_01.jpg" height="226" width="239" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.8</span></span>
</div>
<p class="para">Notice how each processor's TSS and LDT segment descriptor is delimited by two unused segment descriptors.</p>
<p class="para">The segment descriptor pointing to an LDT in Linux typically stores the address of the <span class="fixed">default_ldt</span> variable. The <span class="fixed">default_ldt</span> variable is basically an LDT with a single NULL descriptor. It is declared in <span class="fixed">/usr/src/linux/include/asm-i386/desc.h</span>.</p>
<div class="informalexample">
<pre class="literallayout">
     struct desc_struct
     {
         unsigned long a,b;
     };
</pre>
</div>
<p class="para">The <span class="fixed">default_ldt</span> variable is defined in <span class="fixed">/usr/src/linux/ arch/i386/kernel/traps.c</span>.</p>
<div class="informalexample">
<pre class="literallayout">
    struct desc_struct default_ldt[] =
    { { 0, 0 }, { 0, 0 }, { 0, 0 },{ 0, 0 }, { 0, 0 }};
</pre>
</div>
<p class="para">The reason that Linux can get away with its minimal GDT is that all processes use the same linear address space but are stored in different regions of physical memory. This is very similar in spirit to MMURTL's memory management approach.</p>
<a name="187"></a><a name="IDX-72"></a>
<p class="last-para">Notice the privilege difference between the kernel segments and the user segments. Unlike MMURTL, which gave every segment a privilege of zero, Linux institutes two rings of protection. The kernel executes with privilege level 0x0, and user code executes with privilege level 0x3.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="188"></a><a name="ch02lev2sec15"></a>Linux and Paging</h3>
<p class="first-para">The techniques of segmentation and paging are both used to divide up an address space into distinct regions. So in a way, perhaps the lack of an elaborate segmentation scheme in Linux is merely an effort to avoid being redundant. To implement demand paging and protection, Linux uses Intel's paging facilities.</p>
<div class="section">
<h4 class="sect4-title">Three-Level Paging</h4>
<p class="first-para">In the <a href="LiB0012.html#49" target="_parent" class="chapterjump">previous chapter</a>, I examined what is known as a two-level paging model that uses two bookkeeping data structures: page directories and page tables. Linux adds another data structure and extends the linear address that it uses so that it has a <i class="emphasis">three-level paging model.</i> I assume that this has been implemented to allow Linux to seamlessly extend itself to 64-bit architectures. The three-level paging model is displayed in <a class="internaljump" href="#ch02fig09">Figure 2.9</a>
</p>
<div class="figure">
<a name="189"></a><a name="ch02fig09"></a><span class="figuremediaobject"><a href="images/fig100%5F01%5F0%2Ejpg" NAME="IMG_31" target="_parent"><img src="images/fig100_01.jpg" height="255" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.9</span></span>
</div>
<p class="para">The CR3 control register holds the base address of the page global directory. The highest-order 10-bit section of the linear address stores an offset address into the page global directory and is added to the base address in CR3 to specify a page global directory entry. <a name="190"></a><a name="IDX-73"></a>This entry stores the base address to a page middle directory structure.</p>
<p class="para">The middle 10-bit section of the linear address is added to the base address in the global page directory entry to specify an entry in the page middle directory. The entry in the page middle directory stores the base address of a page table.</p>
<p class="para">The lowest-order 10-bit portion of the linear address is added to the base address in the page middle directory to specify an entry in the page table. This page table entry will specify the base address of a physical 4KB page of memory. The 12-bit portion of the linear address is an offset into the physical page and specifies an actual physical byte of memory.</p>
<div class="qandaset">
<table border="0" cellpadding="0">
<tr class="qandaentry">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a name="LiB10"><b>1.&nbsp;</b></a>
</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">Wait! Hold on a minute! (At least, I hope this is what you are thinking.) The Pentium is a 32-bit processor that deals with 32-bit linear addresses. How does Linux resolve this fact?</p>
</td><td class="td" valign="top" width="8%">
<p class="first-para">
<a href="#LiB9"><img src="images/question.gif" height="24" width="24" alt="As it turns out, Linux assumes that the portion of the linear address that serves as an offset into the page middle directory consists of zero bits. However, the page middle directory is kept in the address resolution cycle for the sake of forward compatibility. It is just that Linux fixes the page middle directory so that it has a single entry. In the case of the 32-bit Pentium, the page global directory reverts to the page directory we know from earlier. These adjustments are illustrated in Figure 2.10 .                 To get a ground-zero look at how the engineers saw their own solution, here is how the Linux source documentation explains the workaround in /usr/src/linux/include/asm-i386/pgtable.h:    /*The Linux memory management assumes a three-level page* table setup. On the i386, we use that, but `fold` the* mid level into the top-level page table, so that we* physically have the same two-level page table as the* i386 mmu expects. */  " border="0"></a>
</p>
</td>
</tr>
</table>
<p class="bold">Answers</p>
<table border="0" cellpadding="0">
<tr class="qandaentry-answer">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a class="internaljump" name="answer.nr-qandaentry.F65A835D-B5B3-4449-9ED4-CD858FB939BF" href="#LiB10"><b>1.</b></a>&nbsp;</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">As it turns out, Linux assumes that the portion of the linear address that serves as an offset into the page middle directory consists of zero bits. However, the page middle directory is kept in the address resolution cycle for the sake of forward compatibility. It is just that Linux fixes the page middle directory so that it has a single entry. In the case of the 32-bit Pentium, the page global directory reverts to the page directory we know from earlier. These adjustments are illustrated in <a class="internaljump" href="#ch02fig10">Figure 2.10</a>.<div class="figure">
<a name="191"></a><a name="ch02fig10"></a><span class="figuremediaobject"><a href="images/fig101%5F01%5F0%2Ejpg" NAME="IMG_32" target="_parent"><img src="images/fig101_01.jpg" height="205" width="282" alt="Click To expand" border="0"></a></span><a name="192"></a><a name="IDX-74"></a>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.10</span></span>
</div>
<p class="para">To get a ground-zero look at how the engineers saw their own solution, here is how the Linux source documentation explains the workaround in <span class="fixed">/usr/src/linux/include/asm-i386/pgtable.h:</span>
</p>
<div class="informalexample">
<pre class="literallayout">
/*The Linux memory management assumes a three-level page
 * table setup. On the i386, we use that, but "fold" the
 * mid level into the top-level page table, so that we
 * physically have the same two-level page table as the
 * i386 mmu expects.
*/
</pre>
</div>
</p>
</td>
</tr>
</table>
</div>
<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">When Linux runs on a 64-bit processor, the 42-bit linear address in the three-level model will represent the 42 least significant bits in a 64-bit linear address. The other, higher-order bits would be assumed to be zero.</p>
</td>
</tr>
</table>
<p class="para">Linux uses a number of C structures to represent table entries. The page directory and the page table themselves are just arrays of these 32-bit entries. These structures are defined in <span class="fixed">/usr/src/linux/include/asm-i386/page.h</span>.</p>
<div class="informalexample">
<pre class="literallayout">
typedef struct { unsigned long pte_low; } pte_t;
typedef struct { unsigned long pmd; } pmd_t;
typedef struct { unsigned long pgd; } pgd_t;
</pre>
</div>
<p class="para">These structures will change for special cases, like when the address bus has been extended to 36 bits or when a 64-bit processor is being used. I am sticking to the run-of-the-mill 32-bit Pentium scenario for the sake of simplicity.</p>
<p class="para">Remember from the <a href="LiB0012.html#49" target="_parent" class="chapterjump">previous chapter</a> that it is the duty of the operating system to maintain the state of the present flag (P) in the page table. It is also the duty of the operating system to clear the dirty bit (D) when a page is loaded into memory. The processor will set the dirty bit the first time that the page is accessed. This entails accounting work on the part of the operating system. To this end, Linux uses a set of macros to perform its accounting. For example, the following macros are used to query the P flag in the page table entry, set the page table entry, and clear the page table entry:</p>
<div class="informalexample">
<pre class="literallayout">
#define _PAGE_PRESENT   0x001
#define _PAGE_PROTNONE  0x080    /* If not present */