CSE203 Linux Programming

Memory Management

Dr S.Rajarajan
SoC/SASTRA
• Memory is among the most basic, but also most essential,
of resources available to a process.
• This chapter covers the management of this resource:
– the allocation
– Manipulation
– and eventual release of memory.
 The Process Address Space
• Linux, like any modern operating system, virtualizes its
physical resource of memory.
• Processes do not directly address physical memory.
• Instead, the kernel associates each process with a unique
virtual address space.
• This address space is linear, with addresses starting at zero,
increasing contiguously to some maximum value.
• The address space is also flat (unpartitioned): it exists in one
space, directly accessible, without the need for segmentation
 Pages and Paging
• Memory is composed of bits, of which (usually) eight make a
byte.
• Bytes compose words.
• A Word is defined as specific number of bits which can be
processed together (i.e. in one attempt) by the machine/system.
• Alternatively, we can say that Word defines the amount of data
that can be transferred between CPU and RAM in a single
operation
• Pages composed of words
• For the purposes of memory management, the page is the most
important of these: it is the smallest addressable unit of
memory that the memory management unit (MMU) can
manage.
• Thus the virtual address space is carved up into pages.
• The machine architecture determines the page size.
• Typical sizes include 4 KB for 32-bit systems and 8 KB for
64-bit systems
• A 32-bit address space (232 ) contains roughly a million 4
KB pages; a 64-bit address space with 8 KB pages
contains several magnitudes more
• A process cannot necessarily access all of those pages; they
may not correspond to anything.
• Thus, pages are either valid or invalid.
• A valid page is associated with an actual page of data,
either in physical memory (RAM) or on secondary storage,
such as a swap partition or file on disk.
• An invalid page is not associated with anything and
represents an unused, unallocated piece of the address
space.
• Accessing an invalid page results in a segmentation
violation
• If a valid page is associated with data on secondary storage, a
process cannot access that page until the data is brought into
physical memory.
• When a process attempts to access such a page, the memory
management unit generates a page fault.
• The kernel then intervenes, transparently paging in the data
from secondary storage to physical memory.
• Because there is considerably more virtual memory than
physical memory, the kernel may have to move data out of
memory to make room for the data paging in.
• Paging out is the process of moving data from physical memory
to secondary storage.
• To minimize subsequent page faults, the kernel attempts to
page out the data that is the least likely to be used in the near
future.
 Sharing and copy-on-write
• Multiple pages of virtual memory, even in different virtual address
spaces owned by different processes, may map to a single physical
page.
• This allows different virtual address spaces to share the data in
physical memory.
• For example, at any given moment there is a good chance that
many processes on the system are using the standard C library.
• With shared memory, each of these processes may map the library
into their virtual address space, but only one copy need exist in
physical memory.
• As a more explicit example, two processes may both map into
memory a large database.
• While both of these processes will have the database in their
virtual address spaces, it will exist in RAM only once.
Frame 1
Frame 7
Frame 5
NULL
NULL
NULL

Frame 2
Frame 3
Frame 6
Frame 5
NULL
• The shared data may be read-only, writable, or both
readable and writable.
• When a process writes to a shared writable page, one of
two things can happen.
• The simplest is that the kernel allows the write to occur, in
which case all processes sharing the page can see the
results of the write operation.
• Usually, allowing multiple processes to read from or write to
a shared page requires some level of coordination and
synchronization
 Copy on write
• Alternatively, the MMU can intercept the write operation and raise an
exception; the kernel, in response, will transparently create a new copy
of the page for the writing process, and allow the write to continue
against the new page.
• We call this approach copy-on-write (COW).
• Effectively, processes are allowed read access to shared data, which
saves space.
• But when a process wants to write to a shared page, it receives a unique
copy of that page on the fly, thereby allowing the kernel to act as if the
process always had its own private copy.
• As copy-on-write occurs on a page-by-page basis, with this technique a
huge file may be efficiently shared among many processes, and then
individual processes will receive unique physical pages only for those
pages to which they themselves write.
 Memory Regions
• The kernel arranges pages into blocks that share certain
properties, such as access permissions.
• These blocks are called mappings, memory areas, or
memory regions.
• Certain types of memory regions can be found in every
process:
– The text segment contains a process’s program code, string
literals, constant variables, and other read-only data. In Linux,
this segment is marked read-only and is mapped in directly from
the object file (the program executable or a library).
– The stack contains the process’s execution stack, which grows and
shrinks dynamically as the stack depth increases and decreases. The
execution stack contains local variables and function return data. In
a multithreaded process, there is one stack per thread.
– The heap, contains a process’s dynamic memory. This segment is
writable and can grow or shrink in size. malloc() can satisfy memory
requests from this segment
– The data segment contains initialized static variables, i.e. global
variables and local static variables which have a defined value and
can be modified.
– The bss segment contains uninitialized global variables. These
3

variables contain special values (essentially, all zeros), per the C

standard
• Linux optimizes bss global variables in two ways.
• First, because the bss segment is dedicated to uninitialized
data, the linker (ld) does not actually store the values in
the object file.
• This reduces the binary’s size.
• Second, when this segment is loaded into memory, the
kernel simply maps it on a copy-on-write basis to a page
of zeros, efficiently setting the variables to their default
values
 Allocating Dynamic Memory
• Memory also comes in the form of automatic and static
variables, but the foundation of any memory
management system is the allocation, use, and eventual
return of dynamic memory.
• Dynamic memory is allocated at runtime, not compile
time, in sizes that may be unknown until the moment of
allocation.
• As a developer, you need dynamic memory when the
amount of memory that you will need, or how long you
might need it, varies and is not known before the program
runs
• For example, you might want to store in memory the
contents of a file or input read in from the keyboard.
• Because the size of the file is unknown, and the user may
type any number of keystrokes, the size of the buffer will
vary, and you may need to make it dynamically larger as
you read more and more data.
 malloc
• There is no C variable that is backed by dynamic memory
• The classic C interface for obtaining dynamic memory is
malloc():
• #include <stdlib.h>
• void * malloc (size_t size);
• A successful call to malloc() allocates size bytes of memory
and returns a pointer to the start of the newly allocated
region.
• The contents of the memory are undefined; do not expect
the memory to be zeroed.
• Upon failure, malloc() returns NULL, and errno is set to
ENOMEM.
• Usage of malloc() may be rather straightforward, as in
this example used to allocate a fixed number of bytes:
• char *p;
• /* give me 2 KB! */
• p = malloc (2048);
• if (!p)
• perror ("malloc");
• This example used to allocate a structure:
struct treasure_map *map;
/*
* allocate enough memory to hold a treasure_map stucture
* and point 'map' at it
*/
map = malloc (sizeof (struct treasure_map));
if (!map)
perror ("malloc");
• C automatically promotes pointers of void to any other
pointer type on assignment.
• Thus, these examples do not need to typecast the return
value of malloc() to the lvalue’s type used in the
assignments.
• The C++ programming language, however, does not
perform automatic void pointer promotion.
• Consequently, users of C++ need to typecast malloc()’s
return
char *name;
/* allocate 512 bytes */
name = (char *) malloc (512);
if (!name)
perror ("malloc");
• Because malloc() can return NULL, it is vitally important
that developers always check for and handle error
conditions.
• Many programs define and use a malloc() wrapper that
prints an error message and terminates the program if
malloc() returns NULL.
• By convention, developers call this common wrapper
xmalloc():
• /* like malloc(), but terminates on failure */
void * xmalloc (size_t size)
{
void *p;
p = malloc (size);
if (!p) {
perror ("xmalloc");
exit (EXIT_FAILURE);
}
return p;
}
 Allocating Arrays
• Dynamic memory allocation may also be quite complex
when the specified size is itself dynamic.
• One such example is the dynamic allocation of arrays,
where the size of an array element may be fixed but the
number of elements to allocate is dynamic
• To simplify this scenario, C provides the calloc() function:
• #include <stdlib.h>
• void * calloc (size_t nr, size_t size);
• A successful call to calloc() returns a pointer to a block of
memory suitable for holding an array of nr elements, each
of size bytes.
• Consequently, the amount of memory requested in these two
calls is identical (either may end up returning more memory than
requested, but never less):
int *x, *y;
x = malloc (50 * sizeof (int));
if (!x) {
perror ("malloc");
return −1;
}
y = calloc (50, sizeof (int));
if (!y) {
perror ("calloc");
return −1;
}
 calloc Vs malloc
• The behavior is not identical.
• Unlike malloc(), which makes no such guarantees about the
contents of allocated memory, calloc() zeros all bytes in the
returned chunk of memory.
• Thus, each of the 50 elements in the array of integers y
holds the value of 0, while the contents of the elements in x
are undefined
• Unless the program is going to immediately set all 50 values,
programmers should use calloc() to ensure that the array
elements are not filled with gibberish.
• Users often want to “zero out” dynamic memory, even
when not dealing with arrays.
• memset() provides an interface for setting every byte in a
chunk of memory to a given value.
• Letting calloc() perform the zeroing, however, is faster
because the kernel can provide memory that is already
zeroed
• On failure, like malloc(), calloc() returns NULL and sets
errno to ENOMEM
 Resizing Allocations
• The C language provides an interface for resizing (making larger
or smaller) existing allocations:
• #include <stdlib.h>
• void * realloc (void *ptr, size_t size);
• A successful call to realloc() resizes the region of memory pointed
at by ptr to a new size of size bytes.
• It returns a pointer to the newly sized memory, which may or
may not be the same as ptr.
• When enlarging a memory region, if realloc() is unable to enlarge
the existing chunk of memory by growing the chunk in situ, the
function may allocate a new region of memory size bytes in
length, copy the old region into the new one, and free the old
region.
• On any operation, the contents of the memory region are
preserved up to the minimum of the old and the new sizes.
• Because of the potentiality of a copy, a realloc() operation to
enlarge a memory region can be a relatively costly operation.
• If size is 0, the effect is the same as an invocation of free() on
ptr.
• On failure, realloc() returns NULL and sets errno to ENOMEM
• Let’s consider an example of shrinking a memory region.
First, we’ll use calloc() to allocate enough memory to hold a
two-element array of map structures:
struct map *p;
/* allocate memory for two map structures */
p = calloc (2, sizeof (struct map));
if (!p) {
perror ("calloc");
return −1;
}
/* use p[0] and p[1]... */
• Now, let’s assume we’ve found one of the treasures and
no longer need the second map, so we decide to resize
the memory and give half of the region back to the
system.
• This wouldn’t generally be a worthwhile operation, but it
might be if the map structure were very large and we
were going to hold the remaining map for a long time:
struct map *r;
/* we now need memory for only one map */
r = realloc (p, sizeof (struct map));
if (!r) {
/* note that 'p' is still valid! */
perror ("realloc");
return −1;
}
/* use 'r'... */
free (r);
• In this example, p[0] is preserved after the realloc() call.
Whatever data was there before is still there.
• If the call returned failure, p is untouched and thus still
valid.
• We can continue using it
 Freeing Dynamic Memory
• Unlike automatic allocations, which are automatically
reaped when the stack unwinds, dynamic allocations are
permanent parts of the process’s address space until they
are manually freed.
• The programmer thus bears the responsibility of returning
dynamically allocated memory to the system.
• Both static and dynamic allocations, of course, disappear
when the entire process exits.
• Memory allocated with malloc(), calloc(), or realloc()
must be returned to the system when no longer in use
via free():
• #include <stdlib.h>
• void free (void *ptr);
• A call to free() frees the memory at ptr.
• The parameter ptr must have been previously returned
by malloc(), calloc(), or realloc().
• That is, you cannot use free() to free partial chunks of
memory—say, half of a chunk of memory
• ptr may be NULL, in which case free() silently returns.
• This example allocates n arrays of chars containing
successively larger numbers of elements, ranging from
two elements (2 bytes) up to n + 1 elements (n + 1 bytes).
• Then, for each array, the loop writes the character c into
each byte except the last (leaving the 0 that is already in
the last byte), prints the array as a string, and then frees
the dynamically allocated memory.
• Invoking print_chars() with n equal to 5 and c set to X, we
get the following:
 Memory leak
• Note what the repercussions would be if this example did
not invoke free().
• The program would never return the memory to the
system, and, even worse, it would lose its only reference to
the memory—the pointer s—thereby making it impossible
to ever access the memory.
• We call this type of programming error a memory leak
• Because the C language places full responsibility for
managing memory on the programmer, C programmers
must keep a fastidious eye on all memory allocations.
 Dangling pointer
• Another common C programming pitfall is use-after-free.
• This foible occurs when a block of memory is freed and
then subsequently accessed.
• Once free() is called on a block of memory, a program must
never again access its contents.
• Programmers must be particularly careful to watch for
dangling pointers: non-NULL pointers that nevertheless
point at invalid blocks of memory.
• An excellent tool to detect memory errors in your programs
is Valgrind.
 Managing the Dynamic Data Segment
• Unix systems historically have provided interfaces for directly
managing the data segment.
• brk and sbrk are basic memory management system calls used
in Unix and Unix-like operating systems to control the amount of
memory allocated to the data segment of the process
• In the original Unix system, brk and sbrk were the only ways in
which applications could acquire additional data space at run
time
• Now these functions are typically called from a higher-level
memory management library function such as malloc
• Now most programs have no direct use for these interfaces
because malloc() and other allocation schemes are easier to use
and more powerful
• #include <unistd.h>
• int brk (void *end);
• void * sbrk (intptr_t increment);
• These functions derive their names from old-school Unix
systems, where the heap and the stack lived in the same
segment.
• Dynamic memory allocations in the heap grew upward
from the bottom of the segment; the stack grew downward
toward the heap from the top of the segment.
• The line of demarcation separating the two was called the
break or the break point.
• On modern systems where the data segment lives in its
own memory mapping, we continue to label the end
address of the mapping the break point
 int brk (void *end);
• A call to brk() sets the break point (the end of the data
segment) to the address specified by end.
• On success, it returns 0.
• On failure, it returns −1 and sets errno to ENOMEM.
• A call to sbrk() increments the end of the data segment by
increment bytes, which may be a positive or negative.
• sbrk() returns the revised break point.
• Thus, an increment of 0 provides the current break point:
• printf ("The current break point is %p\n", sbrk (0));
• Deliberately, both POSIX and the C standard define neither of
these functions.
• Nearly all Unix systems, however, support one or both.
 Anonymous Memory Mappings
• Memory allocation in glibc uses a combination of the data
segment and memory mappings.
• The classic method of implementing malloc() is to divide the
data segment into a series of power-of-2 partitions and satisfy
allocations by returning the partition that is the closest fit to the
requested size.
• Freeing memory is as simple as marking the partition as “free.”
• If adjacent partitions are free, they can be coalesced into a
single, larger partition.
• If the top of the heap is entirely free, the system can use brk()
to lower the break point, shrinking the heap and returning
memory to the kernel
• This algorithm is called a buddy memory allocation scheme.
• It has the upside of speed and simplicity but the downside
of introducing two types of fragmentation.
• Internal fragmentation occurs when more memory than
requested is used to satisfy an allocation.
• This results in inefficient use of the available memory.
• External fragmentation occurs when sufficient memory is
free to satisfy a request, but it is split into two or more
nonadjacent chunks.
• This can result in inefficient use of memory (because a
larger, less suitable block may be used), or failed memory
allocations (if no alternative block exists).
• Moreover, this scheme allows one memory allocation to
“pin” another, preventing a traditional C library from
returning freed memory to the kernel.
• Imagine that two blocks of memory, block A and block B,
are allocated.
• Block A sits right on the break point, and block B sits
right below A.
• Even if the program frees B, the C library cannot adjust
the break point until A is likewise freed.
• In this manner, a long-living allocation can pin all other
allocations in memory.
• This is not always a concern as C libraries do not strictly
return memory to the system.
• Generally, the heap is not shrunk after each free.
• Instead, the malloc() implementation keeps freed memory
around for a subsequent allocation.
• Only when the size of the heap is significantly larger than the
amount of allocated memory does malloc() shrink the data
segment.
• A large allocation, however, can prevent this shrinkage.
• Consequently, for large allocations, glibc does not use the
heap.
• Instead, glibc creates an anonymous memory mapping to
satisfy the allocation request
• An anonymous memory mapping is simply a large, zero-
filled block of memory, ready for your use.
• Think of it as a brand new heap, solely for a single
allocation.
• Because these mappings are located outside of the heap,
they do not contribute to the data segment’s
fragmentation.
 Allocating memory via anonymous mappings
has several benefits
• No fragmentation concerns. When the program no
longer needs an anonymous memory mapping, the
mapping is unmapped, and the memory is immediately
returned to the system.
• Anonymous memory mappings are resizable, have
adjustable permissions, and can receive advice just like
normal mappings
• Each allocation exists in a separate memory mapping.
There is no need to manage the global heap.
 Creating Anonymous Memory Mappings
• Perhaps because you want to force the use of a memory
mapping over the heap for a specific allocation, or perhaps
because you are writing your own memory allocation
system, you may want to manually create your own
anonymous memory mapping— either way, Linux makes it
easy
• The system call mmap() creates a memory mapping and
the system call munmap() destroys a mapping:
 Advanced Memory Allocation
• Linux provides a couple of functions that offer low-level
control of glibc’s memory allocation system.
• The first such function allows a program to ask how many
usable bytes a given memory allocation contains:
• #include <malloc.h>
• size_t malloc_usable_size (void *ptr);
• A successful call to malloc_usable_size() returns the actual
allocation size of the chunk of memory pointed to by ptr.
• Because glibc may round up allocations to fit within an
existing chunk or anonymous mapping, the usable space
in an allocation can be larger than requested.
• Of course, the allocation will never be smaller than
requested
• The second of the two functions allows a program to
force glibc to return all immediately freeable memory to
the kernel:
• #include <malloc.h>
• int malloc_trim (size_t padding);
• A successful call to malloc_trim() shrinks the data
segment as much as possible, minus padding bytes,
which are reserved. It then returns 1.
• On failure, the call returns 0.
 Debugging Memory Allocations
• Programs can set the environment variable MALLOC_CHECK_
to enable enhanced debugging in the memory subsystem.
• The additional debugging checks come at the expense of less
efficient memory allocations, but the overhead is often worth
it during the debugging stage of application development
• Because an environment variable controls the debugging,
there is no need to recompile your program.
• For example, you can simply issue a command like the
following:
• $ MALLOC_CHECK_=1 ./rudder
• If MALLOC_CHECK_ is set to 0, the memory subsystem
silently ignores any errors.
• If it is set to 1, an informative message is printed to
stderr.
• If it is set to 2, the program is immediately terminated
via abort().
• MALLOC_CHECK_ changes the behavior of the running
program
 Obtaining Statistics
• Linux provides the mallinfo() function for obtaining statistics
related to the memory allocation system:
• #include <malloc.h>
• struct mallinfo mallinfo (void);
• A call to mallinfo() returns statistics in a mallinfo structure.
The structure is returned by value, not via a pointer.
• Its contents are also defined in <malloc.h>:
• Usage is simple:
• struct mallinfo m;
• m = mallinfo ();
• printf ("free chunks: %d\n", m.ordblks);
• Linux also provides the malloc_stats() function, which prints
memory-related statistics to stderr:
• #include <malloc.h>
• void malloc_stats (void);
• Invoking malloc_stats() in a memory-intensive program
yields some big numbers:
 Stack-Based Allocations
• Thus far, ball of the mechanisms for dynamic memory allocation
that we have studied have used the heap or memory mappings
to obtain dynamic memory
• The other common construct in a program’s address space, the
stack, is where a program’s automatic variables live.
• There is no reason, however, that a programmer cannot use the
stack for dynamic memory allocations.
• So long as the allocation does not overflow the stack, such an
approach should be easy and should perform quite well.
• To make a dynamic memory allocation from the stack, use the
alloca() system call:
• #include <alloca.h>
• void * alloca (size_t size);
• On success, a call to alloca() returns a pointer to size bytes
of memory.
• This memory lives on the stack and is automatically freed
when the invoking function returns
• Usage is identical to malloc(), but you do not need to
(indeed, must not) free the allocated memory.
• Upon return, the memory allocated with alloca() is
automatically freed as the stack unwinds back to the
invoking function.
• This means you cannot use this memory once the
function that calls alloca() returns!
• However, because you don’t have to do any cleanup by
calling free(), the resulting code is a bit cleaner