lib0023.html

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

<tr valign="top">
<td class="td" align="left">
<p class="table-para">PAGE_EXECUTE_READ</p>
</td><td class="td" align="left">
<p class="table-para">Page region can be read and executed</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">PAGE_EXECUTE_READWRITE</p>
</td><td class="td" align="left">
<p class="table-para">Page region can be read, executed, and written to</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">PAGE_GUARD</p>
</td><td class="td" align="left">
<p class="table-para">Access raises a STATUS_GUARD_PAGE exception</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">PAGE_NOACCESS</p>
</td><td class="td" align="left">
<p class="table-para">Page region cannot be accessed</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">PAGE_NOCACHE</p>
</td><td class="td" align="left">
<p class="table-para">Page region cannot be placed in the cache</p>
</td>
</tr>
</tbody>
</table>
<p class="para">Violating any of the policies causes an access violation to be generated. This usually results in the offending program being killed.</p>
<p class="last-para">The PAGE_GUARD macro requires a little extra explanation. This macro causes the memory region allocated to be shielded by a one-time exception. The first time that a program tries to read or write to a PAGE_GUARD memory region, a STATUS_GUARD_PAGE exception is generated. The catch is that the run time will turn off the PAGE_GUARD status of the memory region so that the exception can only be thrown once.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Demand Paging</h4>
<p class="first-para">Windows uses the Present (P) flag in page table entries to support demand paging. Windows also adds a twist to this mechanism by loading a cluster of pages in an effort to reduce the number of page faults that it handles. The size of the page cluster loaded depends on the amount of physical memory available. Given that most machines have at least 32MB of DRAM, page clusters will be either four or eight pages in size.</p>
<p class="para">As I mentioned earlier, disk I/O is an extremely expensive operation and should be avoided by whatever means necessary. Each page fault translates into a read from the disk. Clustering is a clever way to save execution time. It is like shopping at a wholesale food distributor to save trips to the grocery store.</p>
<p class="para">When there are plenty of unoccupied page frames in physical memory, the operating system will load disk-bound pages into these frames when they are requested. However, things get a little more complicated when there are no available page frames to spare. In <a name="257"></a><a name="IDX-110"></a>this case, the operating system has to make a policy decision and decide which pages in physical memory will be removed to make way for the requested pages that are loaded from disk storage. How does the operating system decide which pages to write to disk in order to produce the necessary free space?</p>
<p class="para">Once again, we are faced with a scenario that is like a game of musical chairs.</p>
<p class="para">There are a few standard algorithms, including <i class="emphasis">first in, first out</i> (FIFO) and <i class="emphasis">least recently used</i> (LRU). The FIFO algorithm moves pages to disk that have been in memory the longest. The LRU algorithm is slightly more involved. The LRU algorithm takes into account the number of times that a page in physical memory has been modified. Those pages that have been modified the least are written to disk.</p>
<p class="last-para">Which algorithm does Windows use? This depends on the number of processors that Windows can access on the motherboard. If Windows is running on top of a single processor, a variation of the LRU algorithm is utilized. If Windows has multiple processors at its disposal, it uses the FIFO algorithm. In both cases, the algorithms are applied in the context of working sets. If a page is requested that has been written to disk, Windows will look at the working set that the page belongs to in order to determine which members of the working set should be swapped to disk so that the requested page can be loaded into memory.</p>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="258"></a><a name="ch02lev2sec25"></a>Memory Allocation</h3>
<p class="first-para">When the kernel allocates physical memory for a process, it sets up the allocated memory so that the first address (i.e., the lowest address) is a multiple of 64KB. In other words, processes are aligned in physical memory on a 64KB boundary. The size of the address space reserved for a process is a multiple of the native processor's page size. On a Pentium, an application would be given a plot of real estate in physical memory that is a multiple of 4KB. The Pentium does provide facilities for larger page sizes (i.e., 4MB), but everyone in their right mind sticks to 4KB page sizes (MMURTL, Linux, Windows, etc.).</p>
<p class="para">One of the fringe benefits of being a user process is that each task is constructed with its own heap. <a class="internaljump" href="#ch02fig22">Figure 2.22</a> displays one of the possible memory layouts for a user process. The stack grows down from the highest address, and the heap grows up toward the stack.</p>
<div class="figure">
<a name="259"></a><a name="ch02fig22"></a><span class="figuremediaobject"><a href="images/fig139%5F01%5F0%2Ejpg" NAME="IMG_44" target="_parent"><img src="images/fig139_01.jpg" height="257" 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.22</span></span>
</div>
<a name="260"></a><a name="IDX-111"></a>
<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 exact organization of a program's code, data, stack, and heap sections are a function of the development tools used to build the program. Linkers, in particular, can decide where to place an application's components. The linker will normally process object files in the order in which they appear on its command line. For each object file, the linker will embed program sections into the executable as it encounters them. The <span class="fixed">/DO</span> linker option can be used to alter this behavior so the program's sections are arranged in the Microsoft Default Order.</p>
</td>
</tr>
</table>
<p class="para">Unlike MMURTL, which relies on user mode tool libraries, the Windows operating system provides kernel-level services to manage a task's heap. Windows exposes this functionality through a set of Win32 functions. These user-level calls end up invoking kernel mode code in <span class="fixed">Ntoskrnl.exe</span>. A few of the more relevant functions include <span class="fixed">GetProcessHeap()</span>, <span class="fixed">HeapAlloc()</span>, and <span class="fixed">HeapFree()</span>. The following short program demonstrates how these routines are used.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --heapFun.c-- */</span>

<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">HANDLE hHeap;</span>
    <span style="background-color:d9d9d9">unsigned char *buffer;</span>

    <span style="background-color:d9d9d9">hHeap = GetProcessHeap();</span>
    <span style="background-color:d9d9d9">if(hHeap==NULL){ printf("No heap!\n"); exit(1); }</span><a name="261"></a><a name="IDX-112"></a>
    <span style="background-color:d9d9d9">buffer = HeapAlloc(hHeap,HEAP_ZERO_MEMORY,1024);</span>
    <span style="background-color:d9d9d9">if(buffer==NULL){ printf("No heap space!\n"); exit(1);}</span>

    <span style="background-color:d9d9d9">printf("buffer[511]=%X, buffer has been</span>
            <span style="background-color:d9d9d9">zeroed\n",buffer [511]);</span>
    <span style="background-color:d9d9d9">buffer[512]=0xCA;</span>
    <span style="background-color:d9d9d9">printf("buffer[512]=%X\n",buffer[512]);</span>

    <span style="background-color:d9d9d9">if(HeapFree(hHeap,HEAP_NO_SERIALIZE,buffer))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("have returned memory to the collective\n");</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">When this program is run, you will see:</p>
<div class="informalexample">
<pre class="literallayout">
buffer[511]=0, buffer has been zeroed
buffer[512]=CA
have returned memory to the collective
</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">A process in Windows can also create additional heaps in its linear address space. The <span class="fixed">HeapCreate()</span> function is used to this end.</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">There is a set of older heap management functions, like <span class="fixed">Globalxxx()</span> and <span class="fixed">Localxxx ()</span>. The <span class="fixed">Heapxxx ()</span> functions are meant to replace these artifacts.</p>
</td>
</tr>
</table>
<p class="para">The Windows operating system also has a set of mechanisms so that kernel mode components can allocate memory for themselves. This includes:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">Look-aside lists</p>
</li>
<li class="listitem">
<p class="first-para">Paged memory pool</p>
</li>
<li class="listitem">
<p class="first-para">Non-paged (i.e., locked) memory pool</p>
</li>
</ul>
<p class="para">Look-aside lists are a special-purpose source of fixed-size memory blocks. Look-aside lists are fast because the kernel does not have to waste time searching for memory blocks of a particular size. Look-aside lists use memory borrowed from the kernel's paged and non-paged pools. To take a look at the look-aside lists that the kernel is using, you can use the <span class="fixed">! lookaside</span> kernel debugger command.</p>
<div class="informalexample">
<pre class="literallayout">
kd&gt; !lookaside
!lookaside

Lookaside "nt!CcTwilightLookasideList" @ 80475560 "CcWk"
    Type     =     0000 NonPagedPool
    Current Depth  =        4   Max Depth  =        4
    Size           =       16   Max Alloc  =       64<a name="262"></a><a name="IDX-113"></a>
    AllocateMisses =      193   FreeMisses  =       185
    TotalAllocates =      295   TotalFrees =        291
    Hit Rate       =       34%  Hit Rate   =         36%

Lookaside "nt!IopSmallIrpLookasideList" @ 80478d00 "Irps"
    Type     =     0000 NonPagedPool
    Current Depth  =        0   Max Depth  =        4
    Size           =      148   Max Alloc  =      592
    AllocateMisses =        9   FreeMisses =        0
    TotalAllocates =        9   TotalFrees =        0
    Hit Rate       =        0%  Hit Rate   =        0%
.
.
.
Total NonPaged currently allocated for above lists =     2536
Total NonPaged potential for above lists           =     4048
Total Paged currently allocated for above lists    =        0
Total Paged potential for above lists              =      544
kd&gt;
</pre>
</div>
<p class="para">If you look back at <a class="internaljump" href="#ch02fig19">Figure 2.19</a>, you will see that the operating system reserves significant portions of memory for the paged and locked memory pools/heaps. These pools vary in size, but the maximum pool sizes are hard coded in the kernel's source code. The paged memory pool, whose storage can be written to disk, can be at most approximately 492MB in size. The non-paged memory pool, which is used by device drivers that require resident memory, can be at most 256MB in size.</p>
<p class="para">The kernel's use of its memory pools can be examined with the <span class="fixed">Poolmon.exe</span> program that ships with the Windows Support Tools package. But before you do, you will need to run <span class="fixed">gflags.exe</span> (which also ships with the support tools) and enable <i class="emphasis">pool tagging</i>. Pool tagging allows the kernel to assign a tag to each type of data structure being allocated and freed within the kernel. Statistics can then be gathered for particular data structures. The