lib0023.html

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

<p class="para">You can determine your build and service pack number by opening the Windows Control Panel and clicking on the System icon. The panel marked General should specify the version status of your Windows installation. If your symbols are the wrong version or the debugger cannot find them, the kernel debugger will display an error message having to do with checksums or missing files. I spent several very frustrating hours figuring this out one particular Saturday.</p>
<p class="last-para">Finally, you will need to set the <span class="fixed">_NT_SYMBOL_PATH</span> environmental variable to the directory containing your symbol files (i.e., <span class="fixed">e:\winnt\symbols</span>). The kernel debugger will use this variable to find the symbol files at run time.</p>
</td>
</tr>
</table>
<p class="para">Once I had the kernel's state loaded up, I examined the GDTR register. This stores the base linear address and limit of the GDT. The debugger views GDTR in terms of two smaller registers (GDTR and GDTL). The <span class="fixed">r</span> command is used to view the contents of registers:</p>
<div class="informalexample">
<pre class="literallayout">
kd&gt; r gdtr
r gdtr
gdtr=80036000
kd&gt; r gdtl
r gdtl
gdtl=000003ff
</pre>
</div>
<p class="para">This told me that the GDT resides at a linear address of <span class="fixed">0x80036000</span> and consists of 128 64-bit GDT entries (i.e., <span class="fixed">3FF</span> bytes). I used the dump command to look at the actual GDT entries:</p>
<div class="informalexample">
<pre class="literallayout">
kd&gt; d 80036000
d 80036000
80036000 00 00 00 00 00 00 00 00-ff ff 00 00 00 9b cf 00 ................
80036010 ff ff 00 00 00 93 cf 00-ff ff 00 00 00 fb cf 00 ................
80036020 ff ff 00 00 00 f3 cf 00-ab 20 00 20 24 8b 00 80 ......... . $...
80036030 01 00 00 f0 df 93 c0 ff-ff 0f 00 00 00 f3 40 00 ..............@.
80036040 ff ff 00 04 00 f2 00 00-00 00 00 00 00 00 00 00 ................
80036050 68 00 80 34 47 89 00 80-68 00 e8 34 47 89 00 80 h..4G...h..4G...
80036060 ff ff c0 2a 02 93 00 00-ff 3f 00 80 0b 92 00 00 ...*.....?......
80036070 ff 03 00 70 ff 92 00 ff-ff ff 00 00 40 9a 00 80 ...p........@...
kd&gt;<a name="247"></a><a name="IDX-104"></a>
</pre>
</div>
<p class="para">After that, it was just a matter of sifting through 64-bit length strips of memory. What I came up with was a list of 25 live segment descriptors. The rest were vacant (i.e., the present flag was cleared). Given that a GDT is capable of storing 8,192 64-bit entries, Windows is only using a very small fraction of the possible total entries.</p>
<div class="informalexample">
<pre class="literallayout">
Kernel Segment Descriptors (Privilege = 0)
-------------------------
0000  Bas=00000000 Lim=00000000 Bytes DPL=0 NP
0008  Bas=00000000 Lim=000fffff Pages DPL=0  P Code  RE A
0010  Bas=00000000 Lim=000fffff Pages DPL=0  P Data  RW A
0030  Bas=ffdff000 Lim=00000001 Pages DPL=0  P Data  RW A
0060  Bas=00022ac0 Lim=0000ffff Bytes DPL=0  P Data  RW A
0068  Bas=000b8000 Lim=00003fff Bytes DPL=0  P Data  RW
0070  Bas=ffff7000 Lim=000003ff Bytes DPL=0  P Data  RW
0078  Bas=80400000 Lim=0000ffff Bytes DPL=0  P Code  RE
0080  Bas=80400000 Lim=0000ffff Bytes DPL=0  P Data  RW
0088  Bas=00000000 Lim=00000000 Bytes DPL=0  P Data  RW
00e0  Bas=f7050000 Lim=0000ffff Bytes DPL=0  P Code  RE A
00e8  Bas=00000000 Lim=0000ffff Bytes DPL=0  P Data  RW
00f0  Bas=8042df4c Lim=000003b7 Bytes DPL=0  P Code  EO
00f8  Bas=00000000 Lim=0000ffff Bytes DPL=0  P Data  RW
0100  Bas=f7060000 Lim=0000ffff Bytes DPL=0  P Data  RW A
0108  Bas=f7060000 Lim=0000ffff Bytes DPL=0  P Data  RW A
0110  Bas=f7060000 Lim=0000ffff Bytes DPL=0  P Data  RW A

User Segment Descriptors (Privilege = 3)
-------------------------
0018  Bas=00000000 Lim=000fffff Pages DPL=3  P Code  RE A
0020  Bas=00000000 Lim=000fffff Pages DPL=3  P Data  RW A
0038  Bas=00000000 Lim=00000fff Bytes DPL=3  P Data  RW A
0040  Bas=00000400 Lim=0000ffff Bytes DPL=3  P Data  RW

TSS Segment Descriptors (Used For Multitasking)
-------------------------
0028  Bas=80242000 Lim=000020ab Bytes DPL=0  P TSS32    B
0050  Bas=80473480 Lim=00000068 Bytes DPL=0  P TSS32    A
0058  Bas=804734e8 Lim=00000068 Bytes DPL=0  P TSS32    A
00a0  Bas=8147d468 Lim=00000068 Bytes DPL=0  P TSS32    A
</pre>
</div>
<p class="para">I discovered that my initial suspicions were warranted. Windows, for the most part, makes only minimal use of segmentation. The segmentation scheme that is implemented has only two privilege levels (0 and 3) so that it can rely on paging to do most of the actual memory management and protection.</p>
<a name="248"></a><a name="IDX-105"></a>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="249"></a><a name="ch02lev2sec24"></a>Windows and Paging</h3>
<p class="first-para">The bulk of Windows memory management is built upon paging hardware. Windows uses the Pentium's paging facilities to implement both memory protection and demand paging. As with the last section, I do not have access to the source code that implements paging. This means that I'll have to try and validate the existence of features by looking for related API functions, special tools, and other indirect means.</p>
<div class="section">
<h4 class="sect4-title">Linear Address Space Taxonomy</h4>
<p class="first-para">The memory that constitutes the linear address space of a user application can be classified as one of three different species:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">Free</p>
</li>
<li class="listitem">
<p class="first-para">Reserved</p>
</li>
<li class="listitem">
<p class="first-para">Committed</p>
</li>
</ul>
<p class="para">
<i class="emphasis">Free memory</i> is not being used by an application. To understand reserved and committed memory, it is helpful to use a restaurant analogy. When you call a restaurant and reserve a table, you are not actually sitting at the table, but you know it will be there when you need it. Not until you walk into the restaurant and sit down have you made a commitment to spend money.</p>
<p class="para">Likewise, <i class="emphasis">reserved memory</i> is nothing more than a range of linear addresses that has been set aside for future use. Trying to access linear memory that is reserved produces a page fault because no physical memory has been allocated yet. <i class="emphasis">Committed memory</i> is a range of linear addresses for which physical storage in memory or on disk has been allocated. This two-phase commit, to borrow a phrase from transaction theory, allows memory to be reserved. This approach, which delays physical memory allocation until the last minute, belongs to a school of algorithms known as <i class="emphasis">lazy evaluation.</i>
</p>
<p class="para">The concepts of reserved and committed memory are reflected in the Win32 API. Specifically, there is a function called <span class="fixed">VirtualAlloc()</span> that allows memory to be reserved or committed.</p>
<p class="para">Given that allocation of linear address regions consists of two phases, it only makes sense that the freeing of linear memory is also comprised of two phases. Linear memory is de-committed so that the memory region has reverted to the reserved state, and then it is released. <span class="fixed">VirtualFree()</span> is a Win32 API function that provides this mechanism to user applications.</p>
<p class="para">Consider the following example:</p>
<a name="250"></a><a name="IDX-106"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</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">long *ptr;</span>
    <span style="background-color:d9d9d9">unsigned long nbytes = 1024;</span>
    <span style="background-color:d9d9d9">ptr = VirtualAlloc(NULL,nbytes,MEM_RESERVE,PAGE_READWRITE);</span>
    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">memory is reserved: this will cause application to crash</span>
    <span style="background-color:d9d9d9">ptr[64]='a';</span>
    <span style="background-color:d9d9d9">*/</span>
    <span style="background-color:d9d9d9">VirtualAlloc(ptr,nbytes,MEM_COMMIT,PAGE_READWRITE);</span>
    <span style="background-color:d9d9d9">ptr[64]='a';</span>

    <span style="background-color:d9d9d9">if(VirtualLock(ptr,nbytes)){ printf("page locked\n"); }</span>
    <span style="background-color:d9d9d9">else{ printf("lock failed\n"); }</span>

    <span style="background-color:d9d9d9">if(VirtualUnlock(ptr,nbytes)){ printf("page unlocked\n"); }</span>
    <span style="background-color:d9d9d9">else{ printf("unlock failed\n"); }</span>

    <span style="background-color:d9d9d9">VirtualFree(ptr,nbytes,MEM_DECOMMIT);</span>
    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">memory is reserved: this will cause application to crash</span>
    <span style="background-color:d9d9d9">ptr[64]='a';</span>
    <span style="background-color:d9d9d9">*/</span>
    <span style="background-color:d9d9d9">VirtualFree(ptr,nbytes,MEM_RELEASE);</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">If memory is accessed while it is in the reserved state, the application will crash. You can re-insert the code that has been commented out to prove this to yourself.</p>
<p class="last-para">As with Linux, pages of memory can be locked. User programs can use the <span class="fixed">VirtualLock()</span> and <span class="fixed">VirtualUnlock ()</span> functions to request that a region of linear memory is locked. However, the kernel is free to ignore this request. The only way to guarantee that a region of linear memory is locked is to invoke kernel mode functions like <span class="fixed">MmLockPageableCodeSection ()</span> and <span class="fixed">MmLockPageableDataSection()</span>. Unfortunately, these calls are internal to the kernel and normally cannot be invoked from user space.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Musical Chairs for Pages</h4>
<p class="first-para">In the game of musical chairs, a large group of people compete to occupy a limited number of chairs. There are always a few people who end up without a chair. This is the kind of scenario that a page <a name="251"></a><a name="IDX-107"></a>of memory faces. A page would like to be in physical memory, but there are a limited number of page frames available in DRAM.</p>
<p class="para">A <i class="emphasis">working set</i> is the subset of pages in a linear address space that actually reside in physical memory. Each user application has a working set, known as a <i class="emphasis">process working set</i>. The operating system also has a working set, known as the <i class="emphasis">system working set</i>. If you look at <a class="internaljump" href="#ch02fig19">Figure 2.19</a>, you will see that regions of the operating system's linear address space are reserved for keeping track of process and system working sets. To make efficient use of physical memory, Windows tracks the number of pages allocated to each working set and can expand or trim the number of page frames allotted. The default minimum and maximum working set sizes are depicted in <a class="internaljump" href="#ch02table06">Table 2.6</a>.</p>
<a name="252"></a><a name="ch02table06"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 2.6</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Physical DRAM Available</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Default Minimum</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Default Maximum</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">Less than 20MB</p>
</td><td class="td" align="left">
<p class="table-para">20 pages</p>
</td><td class="td" align="left">
<p class="table-para">45 pages</p>