lib0022.html

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

<li class="listitem">
<div class="informalexample">
<pre class="literallayout">
static inline void * vmalloc (unsigned long size);
</pre>
</div>
</li>
</ul>
<p class="para">The <span class="fixed">__get_free_pages ()</span> function is defined in <span class="fixed">/usr/src/linux/mm/page_alloc.c</span>. It uses the buddy system algorithm to allocate 2<sup>order</sup> pages of contiguous memory. The <span class="fixed">gfp_mask</span> dictates how the free pages will be looked for. For example, if <span class="fixed">gfp_mask</span> is set to <span class="fixed">__GFP_HIGH</span>, the priority of the memory request is set to the highest level. There are a whole set of <span class="fixed">gfp_mask</span> values in <span class="fixed">/usr/src/linux/include/linux/mm.h</span>.</p>
<p class="para">The <span class="fixed">kmalloc()</span> function is defined in <span class="fixed">/usr/src/linux/mm/slab.c</span> and allocates <span class="fixed">size</span> number of bytes. Instead of a buddy system algorithm, it uses an approach similar to the <i class="emphasis">slab allocator</i> designed by Sun Microsystems in 1994. The <span class="fixed">kmalloc()</span> <a name="202"></a><a name="IDX-79"></a>function manages 4KB pages internally so that smaller amounts of memory can be requested.</p>
<p class="para">The <span class="fixed">vmalloc ()</span> function is defined in <span class="fixed">/usr/src/linux/include/linux/vmalloc.h</span>. This function allows noncontiguous pages of memory to be allocated. The two previous functions deal only with contiguous regions of memory. The <span class="fixed">size</span> argument indicates the number of pages to allocate.</p>
<p class="para">The kernel allocates dynamic memory for user applications when the <span class="fixed">sys_fork()</span> system call is made. The <span class="fixed">sys_fork()</span> function causes a <i class="emphasis">process address space</i> to be requisitioned from memory for the user program. A process address space consists of a set of <i class="emphasis">memory regions</i> in the computer's linear address space. Each region is a contiguous set of linear addresses and is assigned a set of access rights. The size of each memory region is a multiple of 4KB.</p>
<p class="para">Linux user applications traditionally have four memory regions. One is used to store the application's machine code, one is used to store the application's data, another serves as a stack, and the fourth region is used as a heap to provide space for run-time storage requests. The arrangement of these regions in the linear address space is a function of the development tools that were used to build the application and operating system's program loader. For example, <a class="internaljump" href="#ch02fig13">Figure 2.13</a> displays two different ways to organize memory regions.</p>
<div class="figure">
<a name="203"></a><a name="ch02fig13"></a><span class="figuremediaobject"><a href="images/fig107%5F01%5F0%2Ejpg" NAME="IMG_35" target="_parent"><img src="images/fig107_01.jpg" height="180" width="238" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 2.13</span></span>
</div>
<p class="para">The <span class="fixed">sys_fork()</span> function in <span class="fixed">/usr/src/linux/arch/i386/kernel/process.c</span> is just a wrapper for <span class="fixed">do_fork()</span>,which takes care of the real work. The <span class="fixed">do_fork()</span> function calls a function named <span class="fixed">copy_mm()</span> to take care of creating the new task's <a name="204"></a><a name="IDX-80"></a>address space. The <span class="fixed">copy_mm()</span> function, in turn, calls a function named <span class="fixed">mm_init()</span>, which eventually ends up in a call to <span class="fixed">___get_free_pages()</span>.</p>
<p class="para">This string of function calls creates a memory descriptor for the new process and populates it. A memory descriptor, in terms of the C programming language, is just a <span class="fixed">mm_struct</span> structure in the file <span class="fixed">/usr/src/linux/include/linux/sched.h</span>.</p>
<div class="informalexample">
<pre class="literallayout">
struct mm_struct
{
    struct vm_area_struct * mmap;
    rb_root_t mm_rb;
    struct vm_area_struct * mmap_cache;
    pgd_t * pgd;
    atomic_t mm_users;
    atomic_t mm_count;
    int map_count;
    struct rw_semaphore mmap_sem;
    spinlock_t page_table_lock;

    struct list_head mmlist;

    unsigned long start_code, end_code, start_data, end_data;
    unsigned long start_brk, brk, start_stack;
    unsigned long arg_start, arg_end, env_start, env_end;
    unsigned long rss, total_vm, locked_vm;
    unsigned long def_flags;
    unsigned long cpu_vm_mask;
    unsigned long swap_address;

    unsigned dumpable:1;

    /* Architecture-specific MM context */
    mm_context_t context;
};
</pre>
</div>
<p class="para">The <span class="fixed">vm_area_struct</span> structure describes a given memory region. Because a process address space usually consists of several memory regions, the <span class="fixed">mm_struct</span> process address space descriptor will need to keep a list of <span class="fixed">vm_area_struct</span> variables. This is what the <span class="fixed">mmap</span> member variable is for.</p>
<p class="para">The <span class="fixed">pgd</span> member variable points to the page global directory allocated to a process address space. Each process in Linux owns a single page global directory, and this points to one or more page tables. Each process also has its own CR3 value. This register's contents are saved in the task's TSS when its corresponding task is suspended.</p>
<a name="205"></a><a name="IDX-81"></a>
<p class="para">The <span class="fixed">total_vm</span> member specifies how many pages have been allotted for a process, and the <span class="fixed">locked_vm</span> field determines how many of these pages are locked. The <span class="fixed">rss</span> member variable indicates the number of page frames in RAM that the process is actually using.</p>
<p class="last-para">There are a number of fields, like <span class="fixed">start_code</span> and <span class="fixed">end_code</span>, that store the initial and final linear addresses of each memory region. The location of command line arguments on the task's run-time stack is specified by the <span class="fixed">arg_start</span> and <span class="fixed">arg_end</span> member variables.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="206"></a><a name="ch02lev2sec18"></a>Memory Usage</h3>
<p class="first-para">For a system-wide summary of memory usage, use the <span class="fixed">free</span> command:</p>
<div class="informalexample">
<pre class="literallayout">
# free
           total     used    free   shared   buffers   cached
Mem:       62200     58916   3284   864      2692      17688
-/+ buffers/cache:   38536   23664
Swap:      96380      9480   86900
Total:    158580     68396   90184
</pre>
</div>
<p class="para">Mem and <span class="fixed">swap</span> are simply physical memory and disk swap space. Linux tends to keep things simple, and this is part of its appeal to me. The data displayed by <span class="fixed">free</span> is actually an abbreviated version of what you would get by looking in the kernel's <span class="fixed">/proc</span> directory:</p>
<div class="informalexample">
<pre class="literallayout">
# cat /proc/meminfo
        total:      used:     free:  shared: buffers:  cached:
Mem:   63692800  39899136  23793664  1110016  6172672 15433728
Swap:  98693120  39428096  59265024
MemTotal:         62200 kB
MemFree:          23236 kB
MemShared:         1084 kB
Buffers:           6028 kB
Cached:            8972 kB
SwapCached:        6100 kB
Active:           10664 kB
Inact_dirty:      11208 kB
Inact_clean:        312 kB
Inact_target:      1780 kB
HighTotal:            0 kB
HighFree:             0 kB
LowTotal:         62200 kB
LowFree:          23236 kB
SwapTotal:        96380 kB
SwapFree:         57876 kB
NrSwapPages:      14469 pages<a name="207"></a><a name="IDX-82"></a>
</pre>
</div>
<p class="para">If you are interested in looking at the memory usage of a particular process, the <span class="fixed">ps</span> command can be applied:</p>
<div class="informalexample">
<pre class="literallayout">
   # ps -o sz,vsz,pmem,pid -C init

   SZ   VSZ %MEM   PID
  353  1412  0.1     1
</pre>
</div>
<p class="last-para">This command pumps out the size in bytes of physical memory used, the size in bytes of linear address space being used, percent of memory used, and the process ID of the <span class="fixed">init</span> command. If you need to determine which tasks are running on a Linux machine in order to use the <span class="fixed">ps</span> command that I just showed you, I would recommend using <span class="fixed">pstree</span>. The <span class="fixed">pstree</span> command displays an ASCII tree of all the tasks currently running.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="208"></a><a name="ch02lev2sec19"></a>Example: Siege Warfare</h3>
<p class="first-para">In the Middle Ages, siege warfare was a common form of battle. A siege would occur when a larger army surrounded a smaller army that was holed up inside a stronghold. The besiegers had two basic options: storm the fortifications or wait the enemy out. Both options could be expensive. War has always been, and still is, founded on financial concerns. Storming the stronghold could be costly in terms of lives. Starving an enemy into submission was also expensive because it cost a significant amount of money to sustain a standing army in terms of food and supplies. Although movies may favor the storming tactic, some of the more spectacular victories were obtained through patience.</p>
<blockquote class="blockquote">
<p class="first-para">"So, you think you could out-clever us French folk with your silly knees-bent running about advancing behavior?"</p>
<p class="last-para">&mdash; French guard, <I>Monty Python and the Holy Grail</I>
</p>
</blockquote>
<p class="para">Because Linux has a two-ring privilege scheme, the innards of the operating system are not exposed and vulnerable like they are in DOS. We cannot simply rip out entries in the interrupt vector table or write messages to the screen by modifying VRAM. We are back in elementary school: To do anything, we need permission. The kernel policies, in conjunction with Intel hardware, have built fortifications against malicious programs. The crown jewels, operating system data structures, have been hidden far behind thick, formidable walls.</p>
<p class="para">In this example, I will lay siege to Linux in an attempt to demonstrate its memory protection facilities. As in the Middle Ages, I can either storm the walls or wait it out. I suspect that waiting it out and <a name="209"></a><a name="IDX-83"></a>starving the kernel of resources is still the most effective way to bring a computer to its knees. An example of this kind of attack would be a memory leak.</p>
<p class="para">I ran the following program on Linux:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --starve.c-- */</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">unsigned long i;</span>
    <span style="background-color:d9d9d9">unsigned long j;</span>
    <span style="background-color:d9d9d9">char ch;</span>
    <span style="background-color:d9d9d9">unsigned char *ptr;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;0XFFFFFFFF;i++)</span>
    <span style="background-color:d9d9d9">{</span>

        <span style="background-color:d9d9d9">printf("malloc(%lu)\n",i);</span>
        <span style="background-color:d9d9d9">ptr = malloc(0x100000);</span>
        <span style="background-color:d9d9d9">for(j=0;j&lt;0x100000;j++){ ptr[j]=0x7; }</span>
        <span style="background-color:d9d9d9">printf("press [enter] key\n");</span>
        <span style="background-color:d9d9d9">scanf("%c",&amp;ch);</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">The machine I tested this code on had 64MB of DRAM. At about 110MB of allocated virtual memory, my computer's paging subsystem began to thrash. A few moments later, I lost control of my machine; I couldn't even gain the attention of a terminal console to kill the process. I literally had to unplug my computer. A more insidious version of this program would sleep at odd intervals and only allocate small bits of memory. This kind of attack tends to creep up on systems that aren't being monitored carefully.</p>
<p class="para">Next, I tried the more audacious approach of directly assaulting the kernel:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --brute.c-- */</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned char *ptr;</span>
    <span style="background-color:d9d9d9">ptr = 0XC00000000;</span>
    <span style="background-color:d9d9d9">*ptr ='a';</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">Here is the console output that I received:</p>
<div class="informalexample">
<pre class="literallayout">
[root@localhost root]# cc -o brute brute.c<a name="210"></a><a name="IDX-84"></a>
[root@localhost root]# ./brute
Segmentation fault
</pre>
</div>
<p class="para">"You silly King..." As you can see, the Linux kernel has been heavily fortified against such brazen direct attacks. It noticed my attempt for access to the kernel's memory image and sent me to <span class="fixed">/dev/null</span>. Trying this type of straightforward tactic is about as wise as starting a land war in Asia. Inconceivable.</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">However, there is an option that I haven't mentioned. The goal of storming a stronghold is to get inside. There are other, less obtrusive ways of getting past a heavy stone barrier. At the end of the day, nothing beats a generous plateful of treachery. Why spend man-hours of effort to break down a wall when you can sneak by it?</p>
</td>
</tr>
</table>
<p class="para">Linux Loadable Kernel Modules (LKMs) present the besieging army with an opportunity to dress up like opposing troops and simply walk blithely through the main gate. LKMs are basically software components that can be dynamically added to the kernel image, which is loaded in memory, at run time. An LKM becomes a part of the executing kernel. Why spend all that effort trying to pass a fortification when you can start on the other side to begin with?</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">Once an LKM has been merged with the kernel's image, the LKM's code is a DOS-like situation where the operating system is naked. In this state, we can write to any device files we want. This includes <span class="fixed">/dev/kmem</span>, the kernel's coveted memory image. We can also modify the <span class="fixed">/proc</span> file system or perhaps hook an internal kernel function. The potential number of uses is almost infinite. Ba ha ha ha ha (evil laugh).</p>
</td>
</tr>
</table>