Pointers and Memory Allocation

Introduction

So far you have been statically declaring variables so that the compiler allocates an appropriate amount of memory for the variables indicated in your program. In this section we learn that it is possible to allocate memory dynamically.

Constraints of Data on the Run-time Stack

Variables, arrays, and structs are essential for many programming tasks, but in our use thus far they all have a common weakness:

When any variable is declared for storage on the run-time stack, the size of the entity must be specified at compile time.

Once space is allocated for a variable, array, or structure on the run-time stack, that space cannot be expanded. Subsequent variables may be declared, so the space both before and after a given variable may already be allocated to something else, and therefore expansion for a variable's storage is impossible.

In many applications, we may be able to anticipate what data might be expected, and we can make a reasonable guess regarding how much space might be required. However, such guessing has at least three drawbacks.

Altogether, in some applications, having to anticipate the size of data sets (or arrays) can create substantial practical difficulties. We therefore will need a more dynamic method for allocating (and freeing) space as the program runs.

Dynamic Memory Allocation

Rather than allocate all memory at the start of the main function or when a function is called, a program might allocate space only as needed. Then, when the program no longer needs that space, the space may be deallocated. Such an approach is called dynamic memory allocation.

As we shall discover in this course segment, the basics of dynamic memory allocation require at least three fundamental components:

1) A Mechanism to Allocate and Deallocate Space
Within a program, there must be a way to allocate an appropriate amount of space as it is needed, and there must be another mechanism to deallocate the space when that material is no longer needed. In C, readings and labs will illustrate the functions malloc (memory allocation) and free that perform the needed allocation and deallocation.

2) Pointers: Varibles to Store Addresses
Once memory has been allocated, we will find that the concept of pointers, which we already have used in other contexts, will provide a powerful mechanism to keep track of memory that has been allocated.

3) Flexible Data Structures
Once memory is allocated, we must organize data effectively to allow efficient processing. In this course segment, we will examine one widely-used and powerful structure for storing data in flexible structures, called a linked list. Later courses likely will examine additional dynamic data structures, as well.

This course segment explores these components of dynamic memory allocation and dynamic data structures at some length.

Take Heart

Typically, the concepts of dynamic memory allocation and data structures are quite new and different to most students. Even students with considerable computing background often find these topics unfamiliar. Further, the ideas of dynamic storage may not immediately connect with previous topics covered in this course.

Dynamic memory allocation and data structures are different!

As with many topics that are unfamiliar, it may take a moderate amount of time (e.g., several weeks) to become comfortable with the material in this course segment.

Don't panic!

The ideas are not likely to come together all at once. With thought and practice, this material will emerge coherently from the initial fog (even if it may not seem so at various points in the next several labs). At first, a fog may seem disconcerting, and you may lose your bearings occasionally. Over time, fog may lift partially and then come back; understanding may seem to be emerging one day, but then foggier the next day—for awhile.

Eventually, with patience the fog will clear, and the new scenery will appear with much deeper levels of understanding and mastery

Courage — you'll get this, just be patient and keep going!

Textbook Reading

Now, examine all the details with a reading from your textbook:

Allocating Space: Stack versus Heap

Statically declared variables are allocated space on the runtime stack as functions are called and deallocated as they return. As the name implies, because the size of each element is known and never changes we can easily stack them as we nest more deeply into functions; they are easily deallocated as a group.

Dynamically allocating memory requires a different location for storage, called the heap. As the name implies, this area is much less orderly, particularly as elements of various sizes get allocated and deallocated.

Most runtime systems for C treat all the available memory to the program as a giant [meta]-array, with elements on the stack growing and shrinking from one end, while the heap grows, shrinks, or gets holes (perhaps requiring a form of compaction) from the other end.

To visualize, consider the following example program snippet.

double arr1 [5];
double * arr2 = malloc (5*sizeof(double));

arr1[0] = 3.1;
arr1[1] = 4.1;
arr1[2] = 5.9;
arr1[3] = 2.6;
arr1[4] = 5.3;

arr2[0] = 3.1;
arr2[1] = 4.1;
arr2[2] = 5.9;
arr2[3] = 2.6;
arr2[4] = 5.3;

for (int i = 0; i < 5; i++)
   printf ("%lf", arr1[i]);
printf ("\n");

for (int i = 0; i < 5; i++)
   printf ("%lf", arr2[i]);
printf ("\n");

The diagram below provides a schematic view of program memory for this code segment.

Stack-Heap Memory Diagram

When a program starts to execute, the operating system allocates main memory for the entire process, including space for the code itself, space for global variables, and space for the run-time stack and heap.

Traditionally, the run-time stack is located at one end of a large block of memory, and the heap at the other end of that large block. As procedures are called, additional space is needed by the run-time stack, so that part of memory expands toward the unallocated middle of the large memory block. As procedures return, space is deallocated for the run-time stack, and the run-time stack contracts. If you are curious, here is a little more on the subject of the run-time stack (option reading).

In the diagram, the run-time stack is at the left, so the run-time stack expands to the right when a procedure is called and moves back to the left when the procedure is finished. malloc allocates space on the heap, and free deallocates space on the heap. Overall, the heap tends to grow from toward the left in the diagram as malloc is called, and the heap may contract toward the right with free.

In the above code, the program declares two variables, arr1 and arr2. Since these are declared variables, both are stored on the run-time stack. arr1 is an array of 5 double values, so the entire block of these values is allocated on the run-time stack. The subsequent assignment statement places values within this array. arr2 is only a pointer to a double, so the space allocated on the run-time stack for arr2 is just large enough to store an address. When malloc is called, space is allocated on the heap. The base address of this space is returned by malloc and stored in arr2. A reference to arr2[0] goes to the base address stored in the arr2 variable—that is, arr2[0] refers to the zeroth element in the block of memory that has been allocated on the heap.

Checking for Success

When there is not enough space in the heap to satisfy a request for memory, the NULL pointer will be returned. Thus, every call to malloc must be followed by a check for success. (If you forget to check for success, you may get a segmentation fault by dereferencing a null pointer.)

The proper way to report this error is to use the perror function of the standard I/O library, which prints a message regarding the most recent error that occurred in any system or C library call. Its usage may look something like this:

if (arr2==NULL)
{
  perror("Error creating array");          
  // Take other action, perhaps returning an error code or exiting the program
}

Now, if our call to malloc failed, we would see a message like the following.

Error creating array: Cannot allocate memory

Example Programs

We may review some of the following example programs in class.