Kernel Memory Management

The term "memory" is an overloaded one, and concepts like virtual memory conflate the notion of disk storage and main memory; in turn, the OS's caching of file content in memory (an optimization to speed up access to persistent file data) can make these concepts even more of a muddle.

The first topic we deal with is an introduction to the kernel-side of the memory-related portions of the system call API, and the second is a look at the inner workings of kernel memory management itself. We will take a step back and consider how the Linux kernel handles different memory management tasks, including:

supporting virtual memory (caching memory pages, caching files in memory)
managing its own memory allocation needs
managing the data structures for memory pages on behalf of userlevel tasks

brk(2) implementation

We pick up in the first topic with our examination of the brk system call.

the mm_struct http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/include/linux/mm_types.h#L202
the brk(2) entry point: http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/mm/mmap.c#L246
the do_brk() helper function: http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/mm/mmap.c#L1993
the helper routine for finding a vma intersection http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/include/linux/mm.h#L1211
the find_vma routine: http://lxr.cpsc.ucalgary.ca/lxr/#linux+v2.6.32/mm/mmap.c#L1480

Refer back to the userland example from earlier this week (a demonstration of malloc(3)'s behavior as supported by the kernel (mmap, brk, etc.))

Code for demonstrating compiler-declared size of userland structures and how malloc operates by exploring the data "around" a returned pointer.
A program called break that invokes mmap to try to allocate a single byte.
Sample output for the break program (see what it actually does to the processes memory regions list).

The grab.c program attempts to allocate a structure, copy data into that structure, and then iterate over memory "forever". In reality, what it does is iterate over the process's memory starting at 8 bytes before the allocate structure until the end of the heap.

Eventually, this code will cause a SIGSEGV for referencing an address that is outside the heap memory region.

 char* c = NULL;
 struct aircraft* a = NULL;
 a = (struct aircraft*)malloc(sizeof(struct aircraft));
 if(NULL==a)
 {
   fprintf(stderr, "malloc failed\n");
   return;
 }else{
   fprintf(stdout, "glibc allocated memory at %p\n", a);
 }
 memcpy(a, g_a, sizeof(struct aircraft));
 c = (char*)a;
 c -= 8;
 for(;;)
 {
   fprintf(stdout, "address [%p] stores value [0x%08x]\n", c, *c);
   fflush(stdout);
   c++;
   i++;
   if(sleepon)
     sleep(1);
 }
 return;

Running this program, getting its pid, and then displaying the memory regions of the PAS shows the heap being valid from 09a7a000 to 09a9b000.

(eye@mordor kmem)$ ps aux | grep grabx
eye       6374  1.0  0.0   2000   428 pts/6    S+   13:08   0:00 ./grabx
eye       6376  0.0  0.0   4356   732 pts/7    S+   13:08   0:00 grep grabx
(eye@mordor kmem)$ cat /proc/6374/maps
0058c000-005aa000 r-xp 00000000 08:03 404092     /lib/ld-2.12.so
005aa000-005ab000 r--p 0001d000 08:03 404092     /lib/ld-2.12.so
005ab000-005ac000 rw-p 0001e000 08:03 404092     /lib/ld-2.12.so
005b2000-00742000 r-xp 00000000 08:03 404104     /lib/libc-2.12.so
00742000-00743000 ---p 00190000 08:03 404104     /lib/libc-2.12.so
00743000-00745000 r--p 00190000 08:03 404104     /lib/libc-2.12.so
00745000-00746000 rw-p 00192000 08:03 404104     /lib/libc-2.12.so
00746000-00749000 rw-p 00000000 00:00 0 
008fb000-008fc000 r-xp 00000000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 08:03 412486     /home/eye/457/lectures/memory/kmem/grabx
08049000-0804a000 rw-p 00000000 08:03 412486     /home/eye/457/lectures/memory/kmem/grabx
09a7a000-09a9b000 rw-p 00000000 00:00 0          [heap]
b775a000-b775b000 rw-p 00000000 00:00 0 
b7767000-b7769000 rw-p 00000000 00:00 0 
bff26000-bff3b000 rw-p 00000000 00:00 0          [stack]
(eye@mordor kmem)$

Here is the running program; we can see it eventually attempt to iterate past 0x9a9afff + 1, which is 0x9a9b000, which is outside the valid range of heap addresses. The MMU steps in, raises a memory violation, the kernel catches this event, determines that it is not a recoverable page fault (for example, like one due to a memory page being swapped out for virtual memory), and generates a SIGSEGV signal. Normally this would simply terminate the program, but our program has a signal handler, catches the signal, outputs a message, and then aborts.

(eye@mordor kmem)$ ./grabx
sizeof(int) = 4
sizeof(char) = 1
sizeof(long) = 4
sizeof(struct aircraft) = 12
address of a is = 0xbff38d38
glibc allocated memory at 0x9a7a008
address [0x9a7a000] stores value [0x00000000]
address [0x9a7a001] stores value [0x00000000]
address [0x9a7a002] stores value [0x00000000]
address [0x9a7a003] stores value [0x00000000]
address [0x9a7a004] stores value [0x00000011]
address [0x9a7a005] stores value [0x00000000]
address [0x9a7a006] stores value [0x00000000]
address [0x9a7a007] stores value [0x00000000]
address [0x9a7a008] stores value [0xffffffef]
address [0x9a7a009] stores value [0xffffffbe]
address [0x9a7a00a] stores value [0xffffffad]
address [0x9a7a00b] stores value [0xffffffde]
address [0x9a7a00c] stores value [0x00000041]
address [0x9a7a00d] stores value [0xffffff8e]
address [0x9a7a00e] stores value [0xfffffff3]
address [0x9a7a00f] stores value [0xffffffbf]
address [0x9a7a010] stores value [0xffffffea]
address [0x9a7a011] stores value [0x0000001d]
address [0x9a7a012] stores value [0xffffffad]
address [0x9a7a013] stores value [0xffffffab]
address [0x9a7a014] stores value [0xfffffff1]
address [0x9a7a015] stores value [0x0000000f]
address [0x9a7a016] stores value [0x00000002]
address [0x9a7a017] stores value [0x00000000]
address [0x9a7a018] stores value [0x00000000]
address [0x9a7a019] stores value [0x00000000]
address [0x9a7a01a] stores value [0x00000000]
address [0x9a7a01b] stores value [0x00000000]
address [0x9a7a01c] stores value [0x00000000]
...
address [0x9a9aff8] stores value [0x00000000]
address [0x9a9aff9] stores value [0x00000000]
address [0x9a9affa] stores value [0x00000000]
address [0x9a9affb] stores value [0x00000000]
address [0x9a9affc] stores value [0x00000000]
address [0x9a9affd] stores value [0x00000000]
address [0x9a9affe] stores value [0x00000000]
address [0x9a9afff] stores value [0x00000000]
Caught SIGSEGV. Dyin'. loop iterations=135168
(eye@mordor kmem)$