Tutorial : C - Dynamic Memory

Dynamic Memory

Often a program cannot know in advance how much memory it will require. Setting aside “enough”memory, such as defining a char array of sufficient size to hold the largest permitted string, is not convenient in many situations and may be difficult to manage.

Dynamic memory facilitates memory on demand. Memory is requested at runtime as required, and the lifetime of each memory allocation is controlled directly by the programmer.

 

 

Different Memory Areas in C

C has four distinct areas of memory: the constant data area, the static-extent data area, the stack, and the heap. The first of these stores string constants and other data whose values are known at compile time. This area of memory is read-only, and the results of trying to modify it are undefined. The second data area is for variables that are defined extern or static, and so exist for the lifetime of the program. These variables are read-writable. Both of the first two memory areas are allocated when the program begins and destroyed when it terminates, and are managed by the compiler.

The memory area known as the stack is used to store local variables (i.e., variables with automatic extent). A local variable is allocated memory at the point where it is defined and this memory is released immediately as the variable goes out-of-scope. The stack behaves like a last-in-first-out (LIFO) queue. When variables are defined, they are “pushed onto the stack”, and the stack-size increases. And at the end of a block, if several variables go out-of-scope at once, the variables are destroyed, or “popped off the stack”, in reverse order to their allocation. Stack memory allocation is managed entirely by the compiler.

The heap memory area is for dynamically allocated storage and is managed, not by the compiler, but explicitly by the programmer. Requests for memory, and its subsequent destruction, are performed via a set of standard library functions, and the programmer has complete control over the lifetime of an allocated memory block. The flexibility and control provided by heap-allocated memory comes at the price of added responsibility on behalf of the programmer. The compiler does not check that the memory is managed correctly, and dynamic memory errors are a plentiful source of subtle runtime bugs.

It is worth noting that stack memory allocation is generally much faster than heap memory allocation, as stack allocation involves only an increment of the stack pointer, while heap allocation involves much more complex operations. For this reason, stack allocation is often preferred over heap allocation even at the cost of some wasted storage space. For example, an over-size char array, allocated on the stack, is often used to perform string operations rather than an exact-size array created on demand on the heap.

 

 

Standard Memory Allocation Functions

The two key standard library functions for dynamic memory allocation and de-allocation, respectively, are malloc() and free(). The first, malloc() has the following interface,

void *malloc(size_t size)

where size is the number of bytes of memory to allocate, and the return value is a pointer to this requested memory. Notice that the returned pointer is of type void*, which specifies a generic pointer, and can represent a pointer of any type. For example, to create an array of 10 integers, one writes

int *p = malloc(10 * sizeof(int)); /* allocate bytes for 10 integers */

and the return value of malloc() is automatically converted to type int *. It is common to write an explicit cast to the desired type so as to clarify intent.

int *p = (int *) malloc(10 * sizeof(int));

Typically requests for memory using malloc() will succeed, and the returned pointer points to a valid memory location. However, it is possible for the request to fail (e.g., if the available heapspace is full; a rare event on modern machines, but still possible), and when this happens malloc() returns a NULL pointer. It is important to always check the return value of malloc() for NULL so as to prevent invalid attempts to dereference the NULL pointer.

The de-allocation function free() releases memory allocated by malloc(), and returns it to the heap. It has the following interface,

void free(void *)

and is used as follows (continuing from the previous example).

free(p);

The conversion of a pointer of type int* to a pointer of type void* does not require an explicit cast (in C or C++), and so casts of this variety never appear in practice.

There are two other dynamic allocation functions in the C standard library, calloc() and realloc(). The first, calloc(), behaves almost the same as malloc() but, where malloc() returns a block of memory that is uninitialised (i.e., the cells contain arbitrary values), calloc() initialises the block with zeros. The interface for calloc() is slightly different to malloc() as it take two arguments

void *calloc(size_t n, size_t size)

where the first specifies the number of objects in the requested array, and the second specifies the size of the object type. For example, the following statement allocates an array of 10 integers initialised to zero.

int *p = calloc(10, sizeof(int)); /* allocate array of 10 integers, all 0 */

As for malloc(), calloc() returns NULL if the memory request fails.

The final memory allocation function, realloc(), is used to change the size of an existing block of dynamically allocated memory. That is, given a block of memory allocated by malloc(), calloc(), or realloc() itself, realloc() will adjust the size of the allocated memory to the new requested size. The interface of realloc() is as follows.

void *realloc(void *p, size_t size)

where p is a pointer to the current block of memory and size is the new requested size. The return value is a pointer to the resized memory block, or NULL if the request fails. Also, if realloc() is passed a size request of 0, then the memory pointed to by p is released, and realloc() returns NULL. In this case NULL does not indicate failure.

Calling realloc() does not change the existing contents of a memory block. If the block is reduced, then the excess cells are truncated and the values of the remaining cells are left unchanged. If, on the other hand, the block is increased, the old values are retained and the new cells will contain uninitialised (i.e., arbitrary) values. The action of realloc() is to grow or shrink a region of memory. If this can be done in-place, then realloc() might simply adjust certain bounds records and return but, if there is insufficient space in the current region within the heap, then realloc() will allocate a new block of memory of the appropriate size, copy across the values of the previous block, and release the old block. These operations are managed internally by realloc(), but they may affect application code if it has pointers into the old memory block; these pointers will be invalid if the block is copied elsewhere.

 

 

Dynamic Memory Management

Dynamic memory management is the responsibility of the application programmer, with virtually no help from the compiler. The programmer must keep track of various quantities such as object lifetimes, pointers to different memory locations, lengths of arrays, and so forth. Without good coding practices and careful implementation, dynamic memory can be a rich source of runtime errors which are often notoriously difficult to debug.

Consider, for example, the following function, which makes a copy of the string passed to it and returns a pointer to the copy.

1 char *string duplicate(char *s)
2 /* Dynamically allocate a copy of a string. User must remember to free this memory. */
3 {
4 		char *p = malloc(strlen(s) + 1); /* +1 for ’\0’ */
5 		return strcpy(p, s);
6 }

Notice that using dynamic allocation allows us to allocate exactly the right amount of memory to contain the string. The expression strlen(s)+1 is a common idiom for this operation with +1 to cater for the ’\0’ character. Notice, also, that the return value of strcpy() makes for a convenient return of the copy. However, this function is flawed because it fails to check the return value of malloc(), which, if NULL, will crash the program during the copy operation. A corrected version is shown below.

1 char *string duplicate(char *s)
2 /* Dynamically allocate a copy of a string. User must remember to free this memory.*/
3 {
4 		char *p;
5
6 		p = (char *) malloc(strlen(s) + 1); /* +1 for ’\0’ */
7 		if (p != NULL)
8 			strcpy(p, s);
9 		return p;
10 }

This version detects NULL and passes it back to the calling function to perform error handling. While this function is internally correct, it still leaves the responsibility of freeing the dynamic memory to the caller.

char *s;
s = string_duplicate("this is a string");
...
free(s); /* Calling function must remember to free s. */

Neglecting the free(s) statement means that the memory is not released even when s goes out-ofscope, after which the memory becomes non-recoverable. This sort of error is known as a “memory leak”, and can accumulate large quantities of dead memory if the program runs for a long period of time or allocates large data-structures.

Some common errors related to dynamic memory management are listed below.

• Dereferencing a pointer with an invalid address. If a pointer is not initialised when it is defined, it will contain an arbitrary value, such that it points to an arbitrary memory location. The result of dereferencing this pointer will depend on where it points (e.g., no effect, intermittent strange values, or program crash). Writing to memory via an invalid pointer is known as “memory corruption”.

• Dereferencing a pointer that has been freed. This is a special case of the previous error. Once a memory block is released by calling free(p), the pointer p is no longer valid, and should not be dereferenced.

• Dereferencing a NULL pointer. This typically occurs because a system function returns NULL to indicate a problem and the calling function fails to implement appropriate checking. (For many compilers, dereferencing a NULL pointer is a simple bug to find as it causes the program to crash immediately, but this behaviour is not standard.)

• Freeing memory that has already been freed. Passing a previously freed pointer to free() will cause the function to dereference an invalid address.

• Freeing a pointer to memory that was not dynamically allocated. Memory that is not allocated on the heap, but on the stack or constant data area, say, cannot be released by free(). Attempting to do so will have undefined results.

• Failing to free dynamically allocated memory. Dynamic memory exists until it is explicitly released by free(). Failing to do so results in a “memory leak”.

• Attempting to access memory beyond the bounds of the allocated block. Out-of-bounds errors occur if arrays are not properly bounds checked. A particularly common problem is the “off- by-one” array indexing error, which attempts to access elements one-before-the-beginning or one-past-the-end of an array, due to indexing arithmetic being not quite correct.

Good programming practices exist avoid these memory management errors, and following these rules will greatly reduce the risk of dynamic memory related bugs.

• Every malloc() should have an associated free(). To avoid memory leaks and memory corruption, there should be a one-to-one mapping of calls to malloc() and calls to free(). Preferably the call to free() should appear in the same function as the call to malloc() (rather than have one function return a pointer to dynamically allocated memory and expect the calling function to release it). Alternatively, one might write a create() function that allocates memory for an object and a companion destroy() function that frees it.

• Pointers should be initialised when defined. A pointer should never hold an arbitrary value, but should be initialised with either a valid address or NULL, which explicitly marks a pointer as “points nowhere”.

• Pointers should be assigned NULL after being freed. A pointer that has the value NULL cannot be accidentally freed twice, as free(NULL) has no effect.

free(p);
p = NULL;
...
free(p); /* OK, no effect. */

 

 

Example: Matrices

This section presents a more complex example of dynamic memory, which involves functions for creating and destroying matrices. In Section 8.5, an example program shows the creation and use of a fixed-size (3 × 3) matrix, and the matrices created in the following example may be used similarly. The advantage of dynamic memory allocation is that the matrix sizes need not be known in advanced, and can be specified at run time.

The first function allocates memory for a matrix with m rows and n columns. It is created as an array of m pointers, where each pointer points to a row of n elements.

1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the beginning
3 * of the matrix. This function does not check for memory-allocation errors. */
4 {
5 		double **p;
6 		int i;
7
8 		p = (double **)malloc(m * sizeof (double *));
9 		for (i = 0; i < m; ++i)
10 			p[i]=(double *)malloc(n * sizeof (double));
11 		return p;
12 }

The function return value is a pointer-to-a-pointer, so that the matrix elements may be accessed using multi-dimensional array notation as follows.

double **matrix = create_matrix(2,3);
matrix[0][2] = 5.4;

Notice that pointers referring to dynamically allocated memory may be safely returned by a function, as the memory continues to be valid until explicitly destroyed.

The above function will operate correctly unless malloc() returns NULL. Careless function design like this is an all-to-common programming practice and, if malloc() is unable to satisfy the request for more memory, the program will crash. A function that performs appropriate error checking, and returns NULL if malloc() fails, is shown below.

1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the
3 * beginning of the matrix, and NULL if allocation fails. */
4 {
5 double **p;
6 int i;
7 assert(m>0 && n>0);
8
9 /* Allocate pointer array. */
10 p = (double **)malloc(m * sizeof (double *));
11 if (p == NULL) return p;
12
13 /* Allocate rows. */
14 for (i = 0; i < m; ++i) {
15 p[i]=(double *)malloc(n * sizeof (double));
16 if (p[i] == NULL)
17 goto failed;
18 }
19 return p;
20
21 /* Allocation failed, delete already allocated memory. */
22 failed:
23 for (−−i; i >= 0; −−i)
24 free(p[i]);
25 free(p);
26 return NULL;
27 }

7 The assert() checks for logical errors in the program. Specifically, that the calling function does not request matrices of zero or negative size.

10–11 The first memory allocation is the the array of m pointers. If this fails, there is nothing left to do, and the program simply returns NULL.

14–19 The next set of allocations are for each row of the matrix. If any one of these allocations fails, the previous successful allocations must be released before the function returns so as to prevent memory leaks. In the event of an error, the program jumps out of the allocation loop to the error-handling code. This jump demonstrates another legitimate use of goto, which permits simpler code than
would be possible without it.

22–26 The error-handling code first loops through each successfully allocated matrix row and frees them. It then frees the array of pointers. It is critical that deallocation is performed in this order as the row pointers would be invalid if the pointer array was freed first.

The next function is a companion to create_matrix(), which performs appropriate deallocation operations to release the memory representing a matrix object. This function takes as arguments a pointer-to-a-pointer reference to the matrix, and the matrix dimensions m and n. It is important that the same dimensions are passed for the matrix destruction as for its creation, otherwise it will not be released correctly.

1 void destroy matrix(double **p, int m, int n)
2 /* Destroy an (m x n) matrix. Notice, the n variable
3 * is not used, it is just there to assist using the function. */
4 {
5 		int i;
6 		assert(m>0 && n>0);
7
8 		for (i = 0; i < m; ++i)
9 			free(p[i]);
10 		free(p);
11 }

Notice that the argument n is not actually required by the function, and is part of the interface only to match the interface of create_matrix()—to make the function more intuitive to use. If the incorrect value for m were passed to destroy_matrix() the result would be either memory-leaks (m too small) or memory corruption (m too large).

A neat alternative implementation of create_matrix() and destroy_matrix() is shown below, which is both simpler and less error-prone than the previous solutions. These functions illustrate that there are many ways to solve a problem, and often one approach is significantly better than another.

1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the
3 * beginning of the matrix, and NULL if allocation fails. */
4 {
5 double **p, *q;
6 int i;
7 assert(m>0 && n>0);
8
9 /* Allocate pointer array. */
10 p = (double **)malloc(m * sizeof (double *));
11 if (p == NULL) return p;
12
13 /* Allocate entire matrix as a single 1-D array. */
14 q = (double *)malloc(m * n * sizeof (double));
15 if (q == NULL) {
16 free(p);
17 return NULL;
18 }
19
20 /* Assign pointers into appropriate parts of matrix. */
21 for (i = 0; i < m; ++i, q += n)
22 p[i] = q;
23
24 return p;
25 }

1–11 This code is virtually identical to the previous version of create_matrix().

14–18 Rather than allocate each row separately, memory for the entire matrix is allocated as a single block. If this allocation fails, it is a simple matter to free p and return NULL. This implementation completely bypasses the goto and its more complex error-handling code.

21–22 Having allocated memory, the remaining operations cannot fail, and so do not require error checking. The pointers in the pointer array are assigned to elements in the double array at n element intervals—thus, defining the matrix.

The destroy_matrix() code is also greatly simplified by allocating the matrix elements as a single block. First, the size of the matrix is not required, removing the possibility of passing incorrect dimension values. And, second, the deallocation operations are performed in two lines. Note, these lines must occur in the right order as p[0] is invalid if p is freed first.

1 void destroy matrix(double **p)
2 /* Destroy a matrix. Notice, due to the method by which this matrix
3 * was created, the size of the matrix is not required. */
4 {
5 free(p[0]);
6 free(p);
7 }

Given the final versions of the matrix create and destroy functions, a matrix might be used as follows.

double **m1, **m2;
m1 = create_matrix(2,3);
m2 = create_matrix(3,2);
/* Initialise the matrix elements. */
/* Perform various matrix operations. */
destroy_matrix(m1);
destroy_matrix(m2);

 

 

Example: An Expandable Array

This section presents another extended example of dynamic memory allocation, this time to demonstrate the realloc() function. realloc() is a versatile function; it can perform the tasks of both malloc() and free() and, in addition, can adjust the size of an existing dynamically allocated memory block.

In C, an array has fixed size, which is determined at compile-time. Even dynamically allocated arrays have fixed size once they have been created. In certain situations, it may be desirable to have an array that expands on demand as new elements are added to it. That is, to have an array where elements may be added to the end one-by-one, and the array grows to match the number of elements it contains; thus, the array can be built-up without knowing the number of elements in advance. 

In this section, we implement an expandable array of integers. The public interface for this array is exported in a header file vector.h, which is shown below.

1 /* Expandable vector, grows in-place as new elements are added to the back.
2 * The vector memory allocation is exponential to avoid excessive copying. */
3
4 /* Vector access operations. */
5 int push back(int item);
6 int pop back(void);
7 int* get element(int index);
8
9 /* Manual resizing operations. */
10 int get size(void);
11 int set size(int size);
12 int get capacity(void);
13 int set capacity(int size);

5–7 The vector provides three functions for element access. The first, push_back(), adds a new element to the end of the array; the second, pop_back(), returns the last element and then removes it from the array; and the third, get_element(), returns a pointer to a specified array element. The get_element() function permits the expandable vector to be accessed via pointer arithmetic like an ordinary C array.

10–13 In addition to growing the vector by adding elements to the end, there are four functions to provide control of the vector size. The first of these, get_size() and set_size(), obtain and set the size of the vector, respectively. The last two, get_capacity() and set_capacity(), directly control the reserve memory allocation for the array. These functions are explained in more detail below. The implementation of the expandable array is defined in file vector.c. This file hides the private interface, which consists of several constants and external variables, and also hides the module’s dependence on standard headers stdlib.h (for realloc()) and assert.h (for assert()). Arrays by definition occupy a contiguous region of memory, and this creates an issue for developing an expandable array. As the array grows, it becomes necessary to request more memory, and often a region can only be extended so far before there is no more space available.2 At this point,

if realloc() is asked to further extend the memory block, it will allocate a completely new block and copy the data from the old block across to the new one. An array that copies its data from one place to another every time it grows will be very inefficient, and a naive implementation will become increasingly slow. However, with an appropriate allocation scheme, an expandable array can be made to have constant-time complexity on average. The key is to allocate memory in geometrically increasing chunks, so that there is an ever growing amount of free-space allocated as the array size increases. This means that the frequency of allocation, and hence the cost of copying data, decreases with array size at the expense of some wasted space.

1 #include "vector.h"
2 #include <stdlib.h>
3 #include <assert.h>
4
5 static const int StartSize = 1; /* initial vector size */
6 static const float GrowthRate = 1.5; /* geometric growth of vector capacity */
7
8 static int *data = NULL; /* pointer to vector elements */
9 static int vectorsize = 0; /* current size of vector */
10 static int capacity = 0; /* current reserved memory for vector */
11
12 int push back(int item)
13 /* Add element to back of vector. Return index of new element if successful, and -1 if fails. */
14 {
15 		/* If out-of-space, allocate more. */
16 		if (vectorsize == capacity) {
17 			int newsize = (capacity == 0) ? StartSize : (int)(capacity*GrowthRate + 1.0);
18 			int *p = (int *)realloc(data, newsize*sizeof (int));
19 			if (p == NULL)
20 			return −1;
21
22 			capacity = newsize; /* allocate succeeds, update data-structure */
23 			data = p;
24 		}
25
26 		/* We have enough room. */
27 		data[vectorsize] = item;
28 		return vectorsize++;
29 }

8–10 The external variables data, vectorsize, and capacity define the current state of the vector; data points to the array’s dynamic memory block; vectorsize defines the current array size; and capacity records the amount of memory allocated. The value of vectorsize must always be less than or equal to capacity. Notice that these variables are all given initial values, even though they would be initialised to these values by default. Explicit initialisation improves code readability by making ones intentions clear.

16 When a new element is added to the end of the array, its size increases by one. If the vector size is already equal to the amount of available memory, additional memory must be allocated.

17 There are two cases where new memory must be allocated. One, when the very first element is pushed onto the array and, two, when an element is added that exceeds the available space. In the first case, the amount of memory requested will be some initial value StartSize and, in the second, the available memory will be increased by a multiplicative factor GrowthRate. The geometric growth value is increased by one to ensure the allocated size actually increases for small values of capacity.

18–23 The behaviour of realloc() has a few subtle points. If its first argument is NULL, then it acts like malloc() and returns a new block of memory. If the first argument is not NULL, it adjusts the passed memory block to the specified size and returns a pointer to the adjusted block. If the memory request fails, then realloc() returns NULL and the original memory block is unchanged. For this reason, the return value is assigned to a temporary pointer p, rather than

data = (int *)realloc(data, newsize*sizeof(int));

as, in the latter case, the original memory would be lost if realloc() failed. By using a temporary, push_back() can signal a failure while retaining its original state, and will only update its internal data-structures after checking that memory allocation succeeds.

27–28 Once sufficient space is known to be available, the new element is added to the array and the array size is incremented. Notice that the returned value is the value of vectorsize prior to increment, so that it represents the index of the new element.

30 int pop back(void)
31 /* Return element from back of vector, and remove it from the vector. */
32 {
33 		assert(vectorsize > 0);
34 		return data[−−vectorsize];
35 }
36
37 int* get element(int index)
38 /* Return pointer to the element at the specified index. */
39 {
40 		assert(index >= 0 && index < vectorsize);
41 		return data + index;
42 }

30–35 The function pop_back() returns the last element of the array and then deletes it. This operation reduces the size of the array by one, but does not release any memory; capacity remains the same.

37–42 The function get_element() returns a pointer to the element specified by index. This allows the expandable array to be accessed directly and used like an ordinary array. However, pointers returned by this function should be used with caution if the array capacity subsequently changes. When realloc() allocates memory, it may copy the existing data to a new location and then release the old memory. At this instance, any pointers referring to the old memory block are invalidated and should not be dereferenced. Furthermore, if the capacity of the array is reduced, even if realloc() adjusts the memory bounds in-place, pointers referencing beyond the new bounds will be invalid.

43 /* Manual size operations. */
44 int get size(void) { return vectorsize; }
45 int get capacity(void) { return capacity; }
46
47 int set size(int size)
48 /* Set vector size. Return 0 if successful, -1 if fails. */
49 {
50 		if (size > capacity) {
51 			int *p = (int *)realloc(data, size*sizeof (int));
52 			if (p == NULL)
53 				return −1;
54
55 			capacity = size; /* allocate succeeds, update data-structure */
56 			data = p;
57 		}
58
59 		vectorsize = size;
60 		return 0;
61 }
62
63 int set capacity(int size)
64 /* Shrink or grow allocated memory reserve for array.
65 * A size of 0 deletes the array. Return 0 if successful, -1 if fails. */
66 {
67 		if (size != capacity) {
68 			int *p = (int *)realloc(data, size*sizeof (int));
69 			if (p == NULL && size > 0)
70 				return −1;
71
72 			capacity = size;
73 			data = p;
74 		}
75		
76 		if (size < vectorsize)
77 			vectorsize = size;
78 		return 0;
79 }

44–45 These two trivial functions return the current state of the vector in terms of its size and available space, respectively.

47–61 The function set_size() changes the size of the array to the specified size. If this size is greater than the current capacity, then extra memory is allocated to suit. However, if the size is reduced, capacity is left unchanged; this function cannot decrease the available storage.

63–79 The function set_capacity() provides direct access to the memory allocation of the vector. It can be used to increase or decrease the available storage. If the requested size is less than the current vector size, the vector is truncated to fit. If the requested size is zero, realloc() will release the memory pointed to by its first argument and return NULL, effectively deleting the vector. Notice that a request of size zero, will cause data to become NULL (line 73), and vectorsize and capacity to become zero—thus, returning the vector to its original state. 

The above implementation of an expandable array is a good example of modular programming as far as it goes, but it is subject to a couple of serious limitations. First, it provides a single instance of the vector only, and we cannot have more than one in any given program. Second, the vector can only contain elements of type int. To create a vector for other types would require a new, virtually identical, implementation for each type. Neither of these limitations are insurmountable, but they require the use of language features not yet covered, such as structs, unions, typedef, and the void* pointer. The application of these features to writing generic code.