lib0021.html

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

<p class="table-para">0x0</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>
</tr>
</tbody>
</table>
<a name="163"></a><a name="IDX-62"></a>
<p class="para">Obviously, Intel is using what I would call a <i class="emphasis">Flat Segment Model.</i> There is really only a single segment (according to the descriptors) that spans the address space of the processor.</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">MMURTL never uses an LDT, only a single GDT and a single IDT (for interrupt handling). During the boot phase, the MMURTL 16-bit boot sector code loads the 32-bit kernel code from the disk to memory at <span class="fixed">0x6000</span>. The kernel is loaded at <span class="fixed">0x6000</span> to avoid wiping out the BIOS data area, which is still needed. The boot code then points the GDTR and IDTR registers to the GDT and IDT. The GDT and IDT were loaded into memory as a part of the kernel image. The boot sector code then switches the processor to protected mode and jumps to the kernel entry point. Once this has transpired, the kernel will reload itself to address <span class="fixed">0x0</span>. The BIOS code and data, which are overwritten in the process, are no longer needed.</p>
</td>
</tr>
</table>
<p class="para">Because there are only three segment descriptors to index, there are only three segment selectors possible (<span class="fixed">0x8</span>, <span class="fixed">0x10</span>, and <span class="fixed">0x18</span>). Each one indexes a specific descriptor. These three selectors are presented and decomposed in <a class="internaljump" href="#ch02fig03">Figure 2.3</a>:</p>
<div class="figure">
<a name="164"></a><a name="ch02fig03"></a><span class="figuremediaobject"><a href="images/fig90%5F01%5F0%2Ejpg" NAME="IMG_25" target="_parent"><img src="images/fig90_01.jpg" height="75" width="269" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.3</span></span>
</div>
<p class="para">From looking at the descriptors and the selectors, it is easy to see that the entire memory address space has been set to privilege level zero. In addition, the segment limits have all been set to the maximum value (0xFFFFF in 4KB increments). This means that no memory protection scheme is used at the segment level. MMURTL uses the simplest protected mode segment model possible and avoids using any other segment-related features.</p>
<a name="165"></a><a name="IDX-63"></a>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="166"></a><a name="ch02lev2sec9"></a>Paging Variations</h3>
<p class="first-para">I have been using the terms "paging" and "virtual memory" synonymously. The historical motivation for paging was to make use of disk storage to simulate core memory. This traditional use is why I have emphasized the employment of paging as a way to artificially expand a computer's address space. Those tiny little magnets were expensive, and 8KB of core memory could only take you so far.</p>
<p class="para">There are, however, other ways to use paging. If you recall from <a href="LiB0012.html#49" target="_parent" class="chapterjump">Chapter 1</a>, the Pentium's paging facilities take a linear address and map it to a byte in physical memory. This address resolution mechanism allows physical memory to be mapped to an artificial/linear address space. A program running in a linear memory space uses pointers holding linear addresses, which to the program appear to correspond to actual physical memory locations. However, the actual physical location of the program and its data have addresses that are usually much different from the linear values. The nature of the Pentium's paging hardware allows for two distinct uses for virtual memory:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">Virtual-paged memory</p>
</li>
<li class="listitem">
<p class="first-para">Demand-paged virtual memory</p>
</li>
</ul>
<p class="para">In the case of <i class="emphasis">virtual-paged memory</i>, physical memory is broken up into a series of pages. A linear address space is implemented, and the hardware takes care of translating the linear addresses to the physical addresses. The linear address space can be much larger than the physical address space, but <i class="emphasis">you will only be able to manage an amount of memory equal in size to the physical address space</i>. Virtual-paged memory is "virtual" because the addresses being used (i.e., the linear addresses) do not correspond to physical addresses.</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">Virtual-paged memory is virtual memory without disk I/O. Page faults are used in virtual-paged memory to indicate memory access violations. Disk storage is not used to expand a processor's address space.</p>
</td>
</tr>
</table>
<p class="para">
<i class="emphasis">Demand-paged virtual memory</i> is where we bring disk storage into the fray. In this case, not only are the addresses fake (i.e., linear), but they might also resolve to physical bytes that are stored on a disk instead of in physical memory. This method is called demand paging because an operating system that uses demand paging will load pages from disk storage "on demand" when they are needed. In addition to reporting access violations, this form of paging also makes use of page faults in order to determine when pages should be loaded from disk storage.</p>
<a name="167"></a><a name="IDX-64"></a>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="168"></a><a name="ch02lev2sec10"></a>MMURTL and Paging</h3>
<p class="first-para">One important characteristic of MMURTL's paging subsystem is that it does not provide disk-based virtual memory. Specifically, MMURTL does not use a disk drive to artificially expand its address space. Instead, MMURTL merely uses the Intel processor's paging hardware to provide memory protection and memory allocation. In other words, MMURTL implements a virtual-paged memory model. Burgess speculates in his book that support for demand-paged virtual memory might be added in the future.</p>
<p class="para">MMURTL uses paging facilities to map each application to the same linear address region, while having them reside in different physical memory regions. This creates the illusion that all the applications exist in the same region of physical memory. However, it is an illusion. The user applications only share the same linear address region. Their page directories and page tables are distinctly different. This bookkeeping technique allows processes to appear to be in the same place simultaneously, when they are really not.</p>
<p class="para">MMURTL uses a 2GB <i class="emphasis">linear</i> address space. Be careful! I am not talking about physical memory; you don't have to go out and buy 2GB of SDRAM to run MMURTL. The OS owns the bottom 1GB of the fake/linear address space and each application thinks that it owns everything above 1GB. In addition, each user application also thinks that it is the only program running above 1GB.</p>
<p class="para">
<a class="internaljump" href="#ch02fig04">Figure 2.4</a> displays the memory map, as seen by a MMURTL user application.</p>
<div class="figure">
<a name="169"></a><a name="ch02fig04"></a><span class="figuremediaobject"><a href="images/fig92%5F01%5F0%2Ejpg" NAME="IMG_26" target="_parent"><img src="images/fig92_01.jpg" height="212" width="265" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.4</span></span>
</div>
<a name="170"></a><a name="IDX-65"></a>
<p class="para">In reality, what is actually happening is illustrated in <a class="internaljump" href="#ch02fig05">Figure 2.5</a>.</p>
<div class="figure">
<a name="171"></a><a name="ch02fig05"></a><span class="figuremediaobject"><a href="images/fig93%5F01%5F0%2Ejpg" NAME="IMG_27" target="_parent"><img src="images/fig93_01.jpg" height="271" 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.5</span></span>
</div>
<div class="qandaset">
<table border="0" cellpadding="0">
<tr class="qandaentry">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a name="LiB8"><b>1.&nbsp;</b></a>
</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">How can this be done? How can applications share the same linear address memory but still reside in separate regions of physical memory?</p>
</td><td class="td" valign="top" width="8%">
<p class="first-para">
<a href="#LiB7"><img src="images/question.gif" height="24" width="24" alt="The key is in the page tables and page directories. It is possible for a linear address to correspond to two different physical addresses because it is nothing but a series of offsets. The base addresses of items can differ, and this is what results in different locations in DRAM. This is illustrated in Figure 2.6 .                 For example, two applications could exist: A and B. In MMURTL, each application has its own page directory. This means that applications A and B will have different sets of paging data structures. Application A will have base addresses set (base1A, base2A, and base3A) and application B will have base addresses set (base1B, base2B, and base3B). The byte that these two sets reference will be completely different, but the linear address is the same because the linear address is nothing but a set of offsets. " 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.265343C8-3722-4321-95D9-1D93C76F5575" href="#LiB8"><b>1.</b></a>&nbsp;</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">The key is in the page tables and page directories. It is possible for a linear address to correspond to two different physical addresses because it is nothing but a series of offsets. The base addresses of items can differ, and this is what results in different locations in DRAM. This is illustrated in <a class="internaljump" href="#ch02fig06">Figure 2.6</a>.<div class="figure">
<a name="172"></a><a name="ch02fig06"></a><span class="figuremediaobject"><a href="images/fig93%5F02%5F0%2Ejpg" NAME="IMG_28" target="_parent"><img src="images/fig93_02.jpg" height="250" width="350" alt="Click To expand" border="0"></a></span><a name="173"></a><a name="IDX-66"></a>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.6</span></span>
</div>
<p class="last-para">For example, two applications could exist: A and B. In MMURTL, each application has its own page directory. This means that applications A and B will have different sets of paging data structures. Application A will have base addresses set (base1A, base2A, and base3A) and application B will have base addresses set (base1B, base2B, and base3B). The byte that these two sets reference will be completely different, but the linear address is the same because the linear address is nothing but a set of offsets.</p>
</p>
</td>
</tr>
</table>
</div>
<p class="para">Now let's look at how MMURTL implements memory protection. If you recall the page directory and page table entries that were described in the <a href="LiB0012.html#49" target="_parent" class="chapterjump">previous chapter</a>, you should remember that the Intel processor supports two different privilege levels: supervisor and user. Page table entries have a field, consisting of a single bit, to specify the privilege level of the memory page that the entry references. If the field is clear, the page of memory possesses supervisor rights. If the field is set, the page possesses only user privileges.</p>
<p class="last-para">In MMURTL, the kernel and all the device drivers exist at the supervisor level, and the user applications exist at the user level. If a user application attempts to access the kernel, a page fault is thrown and MMURTL responds via the IDT This two-ring privilege scheme based on paging is a compromise between the single-ring scheme of DOS (where there is no distinction between the operating system and user applications) and the elaborate four-ring privilege hierarchy supported by the Pentium's segmentation hardware.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="174"></a><a name="ch02lev2sec11"></a>Memory Allocation</h3>
<p class="first-para">MMURTL provides memory to user applications in 4KB pages. If your application only needs 24 bytes, it will be up to the user space libraries (i.e., <span class="fixed">malloc ()</span>) to take a 4KB page and break it into smaller pieces. MMURTL exposes the following memory allocation system calls to user applications:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">
<span class="fixed">extern far U32 AllocPage(U32 nPages, U8 **ppMemRet);</span>
</p>
</li>
<li class="listitem">
<p class="first-para">
<span class="fixed">extern far U32 DeAllocPage(U8 *pOrigMem, U32 nPages);</span>
</p>
</li>
<li class="listitem">
<p class="first-para">
<span class="fixed">extern far U32 QueryPages(U32 *pdPagesLeft);</span>
</p>
</li>
</ul>
<p class="para">Let's look at each function individually:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">AllocPage</p>
<p class="para">nPages &mdash; The number of 4KB pages to allocate</p>
<a name="175"></a><a name="IDX-67"></a>
<p class="last-para">ppMemRet &mdash; A pointer to a pointer that stores the address of the memory allocated</p>
</li>
<li class="listitem">
<p class="first-para">DeAllocPage</p>
<p class="para">pOrigMem &mdash; A pointer to address of the page to free</p>
<p class="last-para">nPages &mdash; The number of 4KB pages to free (assume pages are contiguous)</p>
</li>
<li class="listitem">
<p class="first-para">QueryPages</p>
<p class="last-para">pdPagesLeft &mdash; A pointer to a variable that will hold the number of free pages left</p>
</li>
</ul>
<p class="para">The <span class="fixed">AllocPage ()</span> function allocates memory in contiguous pages. In addition, the memory address returned is the address of the lowest byte in memory (i.e., the first byte of the first page).</p>
<p class="para">All of these functions return a number of possible error codes. There are dozens of error codes defined in MMURTL's header files. It is important to realize that an error code of zero means that there are no problems.</p>
<div class="informalexample">
<pre class="literallayout">
          #define  ErcOK           0     /* Alls Well */
</pre>
</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">As far as protected mode operating systems are concerned, MMURTL is about as spartan as you can get. There is no demand paging, and the page-based allocation scheme is uncomplicated. In the next two case studies, you will see how much more involved memory management can become.</p>
</td>
</tr>
</table>
<a></a>
</div>
<a></a>
</div>
</div>
</div>
</div>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<td><div STYLE="MARGIN-LEFT: 0.15in;">
<a href="toc.html"><img src="images/teamlib.gif" width="62" height="15" border="0" align="absmiddle"  alt="Team LiB"></a></div></td>
<td valign="top" class="v2" align="right"><div STYLE="MARGIN-RIGHT: 0.15in"><a href="LiB0020.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0022.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>