lib0022.html

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

#define pte_present(x)  ((x).pte_low & (_PAGE_PRESENT |
                                        _PAGE_PROTNONE))
#define set_pte(pteptr, pteval) (*(pteptr) = pteval)
#define pte_clear(xp)   do { set_pte(xp, __pte(0)); } while (0)
</pre>
</div>
<p class="para">There are a multitude of other such flags in <span class="fixed">/usr/src/linux/include/asm-i386/pgtable.h</span>. As with many portions of the <a name="193"></a><a name="IDX-75"></a>Linux code base, these macros take different forms when the kernel is not running on a 32-bit Pentium.</p>
<p class="para">There is also a significant amount of page metadata that is external to Intel's native paging data structures, which is to say that the metadata is relevant to Linux without being mandated by the processor. For example, Linux allows pages to be <i class="emphasis">locked</i>. A locked page of memory cannot be written out to disk. Kernel pages are locked. The kernel also keeps a record of how many processes are using a particular page of memory. These extra features are supported by the <span class="fixed">page</span> structure:</p>
<div class="informalexample">
<pre class="literallayout">
typedef struct page
{
   struct list_head list;    /* -&gt; Mapping has some page lists.*/
   struct address_space *mapping;   /* The inode (or ...)
                                       we belong to. */
   unsigned long index;      /* Our offset within mapping. */
   struct page *next_hash;   /* Next page sharing our hash bucket
                                in the pagecache hash table. */
   atomic_t count;           /* Usage count, see below. */
   unsigned long flags;      /* atomic flags, some possibly
                                updated asynchronously */
   struct list_head lru;     /* Pageout list, eg. active_list;
                                protected by pagemap_lru_lock!!*/
   wait_queue_head_t wait;   /* Page locked?  Stand in line... */
   struct page **pprev_hash; /* Complement to *next_hash. */
   struct buffer_head * buffers;   /* Buffer maps us to a disk
                                      block. */
   void *virtual;            /* Kernel virtual address (NULL
                                if not kmapped, ie. highmem) */
   struct zone_struct *zone; /* Memory zone we are in. */
} mem_map_t;
</pre>
</div>
<p class="para">This structure is defined in <span class="fixed">/usr/src/linux/include/linux/mm.h</span>. The <span class="fixed">count</span> member keeps track of how many processes are using a page. The <span class="fixed">count</span> variable is zero if the page is free. The <span class="fixed">flags</span> member stores 32 Boolean fields. Its first bit, the <span class="fixed">PG_locked</span> field, is used to indicate if a page is locked.</p>
<div class="informalexample">
<pre class="literallayout">
#define PG_locked      0    /*  Page is locked.  Don't touch. */

#define UnlockPage(page) unlock_page(page)
#define PageLocked(page) test_bit(PG_locked,  &amp;(page)-&gt;flags)
#define LockPage(page)   set_bit(PG_locked,  &amp;(page)-&gt;flags)
</pre>
</div>
<p class="para">The macros above are also defined in <span class="fixed">/usr/src/linux/include/linux/mm.h</span>.</p>
<a name="194"></a><a name="IDX-76"></a>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="195"></a><a name="ch02lev2sec16"></a>Page Fault Handling</h3>
<p class="first-para">Page faults are the core mechanism that allow Linux to support memory protection and demand paging. The page fault handler in Linux is a function called <span class="fixed">do_page_fault()</span> defined in <span class="fixed">/usr/src/linux/arch/i386/mm/fault.c:</span>
</p>
<div class="informalexample">
<pre class="literallayout">
void do_page_fault(struct pt_regs  *regs,  unsigned long
                   error_code);
</pre>
</div>
<p class="para">The <span class="fixed">regs</span> argument is a pointer to a structure containing the contents of the registers when the page fault was generated.</p>
<p class="para">The <span class="fixed">error_code</span> argument wraps a 3-bit value that was generated as a result of the page fault. It is this little 3-bit value that is absolutely crucial. It will determine what the kernel will do. If a memory access violation has occurred, the kernel will probably kill the process that made the illegal memory access. Sometimes this means putting the kibosh on the kernel! Linux uses the Supervisor/User flag in page table entries to implement the distinction between kernel code and user code.</p>
<p class="para">If a process has attempted to access a page that is on disk (i.e., its present (P) flag is cleared), the kernel will need to take care of loading the page into memory. This is one feature that definitely separates Linux from MMURTL. MMURTL only uses paging as a way to divide up and manage memory. Linux takes things a step further and allows pages to be swapped to disk storage. Naturally, this requires a whole load of additional instructions and logic, making Linux a far more intricate operating system.</p>
<p class="para">
<a class="internaljump" href="#ch02table03">Table 2.3</a> explains the format of the 3-bit value passed to <span class="fixed">do_page_fault</span> and the information that it stores.</p>
<a name="196"></a><a name="ch02table03"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 2.3</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Bit</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Value</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Meaning</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">0</p>
</td><td class="td" align="left">
<p class="table-para">0</p>
</td><td class="td" align="left">
<p class="table-para">Page fault caused by accessing a page that has its present (P) flag cleared</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">0</p>
</td><td class="td" align="left">
<p class="table-para">1</p>
</td><td class="td" align="left">
<p class="table-para">Page fault caused by invalid access right</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">1</p>
</td><td class="td" align="left">
<p class="table-para">0</p>
</td><td class="td" align="left">
<p class="table-para">Page fault caused by access of type execute or type read</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">1</p>
</td><td class="td" align="left">
<p class="table-para">1</p>
</td><td class="td" align="left">
<p class="table-para">Page fault caused by access of type write</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">2</p>
</td><td class="td" align="left">
<p class="table-para">0</p>
</td><td class="td" align="left">
<p class="table-para">Page fault occurred while the processor was in kernel mode</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">2</p>
</td><td class="td" align="left">
<p class="table-para">1</p>
</td><td class="td" align="left">
<p class="table-para">Page fault occurred while the processor was in user mode</p>
</td>
</tr>
</tbody>
</table>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="197"></a><a name="ch02lev2sec17"></a>Memory Allocation</h3>
<p class="first-para">When Linux boots, the kernel reserves a region of physical memory to store its code and data structures. The pages of memory that constitute this region are locked and cannot be written to disk. The <a name="198"></a><a name="IDX-77"></a>kernel is loaded into physical memory starting at physical address <span class="fixed">0x00100000</span> (i.e., just above 1MB). This is done to avoid overwriting BIOS code at the bottom of memory and VRAM that lies within the first megabyte. The size of the kernel's image in memory is a function of the features that were built into it when it was compiled, so it is not really feasible to give a definite upper boundary to the kernel's region in physical memory. The remaining part of physical memory (not reserved by the kernel, BIOS, or VRAM) is known as <i class="emphasis">dynamic memory</i>. <a class="internaljump" href="#ch02fig11">Figure 2.11</a> displays this basic organization of physical memory.</p>
<div class="figure">
<a name="199"></a><a name="ch02fig11"></a><span class="figuremediaobject"><a href="images/fig105%5F01%5F0%2Ejpg" NAME="IMG_33" target="_parent"><img src="images/fig105_01.jpg" height="235" 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.11</span></span>
</div>
<p class="para">The linear address space is an alternate reality that is created by the kernel and the processor (the programs happen to think it is real). It has little or nothing in common with the actual arrangement of code and data in physical memory. The linear address space of Linux is broken into two basic regions. The linear address range from 0 to <span class="fixed">PAGE_OFFSET-</span>1 is used for user programs. The linear address range from <span class="fixed">PAGE_OFFSET</span> to <span class="fixed">0xFFFFFFFF</span> (4GB) is reserved for the kernel. The <span class="fixed">PAGE_OFFSET</span> macro is defined in <span class="fixed">/usr/src/linux/include/asm-i386/page.h</span> as <span class="fixed">0xC0000000</span>. This means that the kernel uses the last gigabyte of linear memory, and the user applications reside in the first three gigabytes. The layout of the Linux linear address space is displayed in <a class="internaljump" href="#ch02fig12">Figure 2.12</a>.</p>
<div class="figure">
<a name="200"></a><a name="ch02fig12"></a><span class="figuremediaobject"><a href="images/fig106%5F01%5F0%2Ejpg" NAME="IMG_34" target="_parent"><img src="images/fig106_01.jpg" height="254" width="237" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.12</span></span>
</div>
<a name="201"></a><a name="IDX-78"></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">A gigabyte of linear address space does not necessarily translate into a gigabyte of physical memory. For example, if the kernel consumes 4MB of physical memory, only 4MB of linear address space will be active in the operating system's gigabyte of linear memory.</p>
</td>
</tr>
</table>
<p class="para">The kernel can allocate dynamic memory for itself by invoking one of three functions:</p>
<ul class="itemizedlist">
<li class="first-listitem">
<div class="informalexample">
<pre class="literallayout">
unsigned long __get_free_pages(unsigned int
         gfp_mask, unsigned int order);
</pre>
</div>
</li>
<li class="listitem">
<div class="informalexample">
<pre class="literallayout">
void * kmalloc (size_t size, int flags);
</pre>
</div>
</li>