Memory Management

One or more c-source files are compiled and linked to form an executable program-file. The internals of this activity is out of the scope of this article. This program-file, once built can then be executed as many times. Each execution instantiates a process. Multiple instantiations of the same program-file can be done simultaneoulsy. Each of these processes run independant of each other.

At school, we learnt that each process has 4 segments. A brief explanation of each segment is given below.

Each process instantiated from the same program file might share the code segment, but will have its own data, stack and heap segments. This ensures that every process runs privately without trampling on each other. Threads or Light Weight Processes are entities that just have a private stack but can access the same memory. We dont discuss threads/LWP much here.

The article will soon explain each of these segments of a c-program in finer detail by dissecting the executable we get and the process we run, familiarizing with a few tools as we do this activity.

Lets take this sample program

We build the above source file into a program-file and execute it. The assembled-instructions of main and function1 go into the code-segment. The code-segment also consists of the instructions from the many other functions provided as part of standard c library, of which we explicity make use of printf and scanf in our program. The variables global_a, static_c both go into the data-segment. This segment is determined when the process starts and is the same size till the program ends - as we know the list of all global and static variables at link-time, and these remain around till the process ends. The variables local_a, local_b, local_c stay in the stack-frame of main-function, while variables arg_a, parg_b, local_d stay in the stack frame of the function1.

This is a pictorial illustration of the stack at the time function1() is under execution. The stack segment’s memory management will not be covered in this article.

The above program doesn’t allocate any dynamic memory itself. We dont know if printf() or scanf() does.

We use the following functions to meet the dynamic memory needs of a process. Memory obtained via these functions are from the Heap Segment. The memory obtained from these functions is to be explicity managed by the programmer. In simpler words, when a memory is no longer required, the programmer invokes the free() api to let go the memory so that it can be made use again, when the programmer asks for memory.

There are memalign, vmalloc, pvalloc, malloc_usable_size and a few more, but its okay if you didn’t know them. We will see them as we explore later in the article.

The quick review concludes. The article will take you further on how each of the above just works in linux, why a few bugs blow up or get covered up in certain ways, among other topics. The article is rather long. Its okay to read it with breaks (of many days) in between. Fasten your belts and lets dive in.

In linux, all the above segments are made available to a process in the same addressing range via the pointer data-type. The pointer data-type is sufficient to address any location in any of the segments. This is in contrast to a few other operating systems which have different types of pointers - far/near, while linux makes no such distinction. There are different pointer types as seen by compiler, for example apple_t* is different from orange_t*, but this distinction is just at compile time, limited to arithmetic on the pointer and to how much is to be extracted when making pointer de-references. But the actual content of these 2 pointer-types itself is exactly the same. A assignment of pointer of type apple_t* to orange_t* is illegal for a different reason, but the void* in c, can morph silently into any pointer type and any pointer-type can also decay to a void*, as the space necessary to hold any pointer-type is the same. This enables us to store and pass pointers to functions (code-segment), pointers to global-data(data-segment), pointers to local-variables(stack) and pointers obtained from heap freely using the same pointer variable.

For example, in this following code

the result pointer could point to any writable int location. It could be in the stack segment(address of a valid local variable), data-segment(address of a global variable) or from heap-segment. We dont bother qualifying the pointer beyond just the data-type to which it points. The pointer itself takes the same to represent, enabling the above single representation for the pointer, to all segments alike.

Lets take a 32 bit system. Pointer data-types in this system is 32 bits long. This makes the maximum theoretically addressable locations 2^32=4G. 4G locations was an awful lot of space when 32 bit processors were introduced, but is now certainly pretty common-place. Nevertheless in a 32-bit machine, or when compiled in 32-bit mode, a process is simply restricted by this simple pointer-size limitation that it can see no more than 4G different locations, irrespective of the available main memory or swap memory, and has to manage all its memory needs in this space.

Different address locations are used for different purposes - code, stack, heap, data. Among the data, we have read-only data and mutable data. To provide for such different needs, linux manages memory in units of pages. A page is typically 4K in size. Different systems make different choices. 4K is quite a popular choice for many processor architectures and it the size for x86 in 32 bit mode. The concepts are the same for any page size.

Not all processes need all the 4G locations to run. In fact, its still considered gargantaun, to consume so much memory for a single process. Most processes just consume a tiny portion of this theoretical limit. Linux offers a process just about as much memory as it wants and considers the rest of the address values as invalid for the process. This enables linux to send a SEGSEV signal to the process, when it tries to read/write a address that is outside of its allowed range. Processes typically terminate on this signal, the notorious segmentation-fault we are familiar with.

The entire address range is a collection of pages. For example, the 4G individual bytes a process can theoretically have, is a collection of 1M pages with each page 4K long. Since a process doesn’t really use all the memory, out of 1M pages, a tiny fraction - about a few hundred pages are typically used by most small processes. Linux allows each process to delcare the permissions of each page that it owns. Its typically non-sensical to twist the permissions of those pages that are auto-setup as part of load-time. Most page-permissions are edited if at all for those pages, which processes explicitly get during execution. A page could be readble, writable, executable. It could be private or shared with other processes (not necesarily at the same address for the other processes).

Just as its illegal to read/write a memory that is simply not a valid page for the process, its also illegal to do an operation on a page without the valid permission. The process is immediately blessed with SIGSEV by Linux on such violations.

Each process has an address map maintained for it by linux, which indicates which address ranges are valid and which address ranges have what permissions. The fun part is that linux simply exposes this address map to be easily readable via the /proc file system.

For those who haven’t come across this /proc file system yet, there is always a /proc directory in the root directory. This is not a real directory, but a vitual one. This directory contains many files and folders, all of them virtual too. One can just read these files as if they are normal files. Each file displays some information which kernel maintains. There is folder for every process that is currently running, with the folder named on the pid of the process. This folder contains further information pertaining to this single process. The /proc/self is a special folder within the already special /proc folder (the /proc is a kernel maintained folder, so there is no end to what the kernel can adjust within here), which is simply the /proc/pid of the invoking process. man proc elaborates on the various other information available in this data mine.

The address map of a process is visible via the /proc/pid/maps file for any process. Lets just see one sample output.

By using /proc/self, we just got the address-map of the cat process itself.

The columns are

The first column tells the range of the address. The next column gives the permission(rwx) and the shared’ness of the page(private/shared). The next 3 columns are relevant for address’es which are mapped to files - Offset of this range in the physical file, device number where file is present and inode of the file. The last column is the pathname of the file, or one of heap/stack/vdso or empty.

Lets wade over the maps. To begin with, just at the moment when it read this /proc/self/maps file was using only 470 pages, about 1.9Mb out of the available 1M pages(4G). Clearly cat’s memory consumption for this invocation was modest.

We can easily place what each address range is used for. We get cues from the address permissions and the path-name. If we notice the first valid address itself is 0x08048000. The first (134Mb) addresses from 0x0 are left unmapped. This ensure all NULL pointer de-references are immeidately seg-faulted as they dont map to a valid address. The long unmapped region also helps to seg-fault dereferences from any offset from a NULL pointer, as long as the offset is withing 134Mb!

The first 2 ranges are from the cat-program file itself. The permissions of the first range is r-x. Its readable and excecutable. So, this maps to the code part of the cat-program. This is not writable, so any attempt to modify the instructions, while in execution will fault the process. The next range has rw- and is also from the cat-program. This hence is the data part of the cat-program. This contains all the global and static data definied in the cat-program. All the code of the cat program fit into just 4 pages, and all the global variables used fits in just 1 page. It should be noted that even if a program delcared just 1 variable, it would still consume 1 page, as 1 page is the least unit of data the kernels allocates/takes-back to/from a process.

Lets do another simple program and see its address map.

Here is the output of running this program.

Interestingly, just like the cat program our program too starts just at 0x08048000. Our program is even leaner than cat with just 1 page of code segment. The data segment is also just 1 page, although we didn’t declare any global or static variable. Although we dont do any malloc we still see about 33 pages of heap! We dont have to fret at this splurge on part of our build chains. There is 1M pages available. The rest of the pages are quite similar to that of cat, including the stack.

The stack at main was at 0xbfffebe0. The current tip is 20 pages away, 0xbfffe - 0xbffea. We have called some functions, so, we can’t say if the stack really grew up as many pages, or if all programs just start with so much of stack bleesed at birth. There are 2 pages below our main’s stack frame 0xc0000 - 0xbfffe.

Lets study how big the kernel lets our program to grow its stack. We will make use of recursion to just let our program die by itself.

We record the last known tip of the stack in a file. gcc now supports declaring variable sized arrays on stack. We make use of this to control how big each stack frame is. When the above was run with 4096, 1024 and 128, we see that tip of the stack was as follows.

The stack in this system seems to grow till 0xbf8000xxx, about 2046 pages 0xbfffe-0xbf800. That’s about 8Mb of stack.

Lets study how big the kernel lets our program to grow its heap. We will make use of interation and a linked list to just keep acquiring memory. Unlike the stack, when heap is no longer available, malloc returns a NULL to let us know. We use the memory obtained to chain them, and later release them. We print the address-map before any malloc, after all malloc and after all free.

Upon running this program, we get the following before the malloc started. This is comparable to what we have been getting.

Now with a size of 1024, after all malloc, we see that the map is as follows. Only the new/changing ranges are shown for brevity

So, our program took the break point to the farthest extreme that the kernel would let a process go towards. Interestingly, our program also managed to get some memory in the 0x0004800 range too and some more from the 0xb8002000 range too. What more, the after-free output is same as the output after all mallocs. Apparently the free doesn’t let go off the memory back to the OS, but just keeps the memory with it, anticipating more mallocs.

The functions malloc and its cousins are user-space functions. They are part of the libc library too, just as most other standard c library functions like printf and scanf are. What this means is that malloc’s implementation by itself is limited to the book-keeping of kernel-given addresses. When that is exhausted, and a malloc() is invoked, malloc() will have to ask the kernel to add more memory to this process. This is done by making system-calls, which augment the valid ranges to the process.

There are 2 system calls which malloc library uses.

We will discuss all the gory details of malloc library in a later section. At the moment, we will just get a high level picture of the requirements of the malloc library.

While its desirable to just hold the current memory requirement of the application and release excess memory to the kernel, this will impact performance of the application, as frequent interaction with the kernel for memory related operations involve context switches between kernel-mode and user-mode. So, the malloc library will have to take a judicious call between making system-calls frequently and holding excess memory.