Chapter 11: Memory Allocation

In this chapter, we’ll meet malloc, C’s dynamic memory allocation function, and we’ll cover dynamic memory allocation in some detail.

As we begin doing dynamic memory allocation, we’ll begin to see (if we haven’t seen it already) what pointers can really be good for. Many of the pointer examples in the previous chapter (those which used pointers to access arrays) didn’t do all that much for us that we couldn’t have done using arrays. However, when we begin doing dynamic memory allocation, pointers are the only way to go, because what malloc returns is a pointer to the memory it gives us. (Due to the equivalence between pointers and arrays, though, we will still be able to think of dynamically allocated regions of storage as if they were arrays, and even to use array-like subscripting notation on them.)

You have to be careful with dynamic memory allocation. malloc operates at a pretty “low level”; you will often find yourself having to do a certain amount of work to manage the memory it gives you. If you don’t keep accurate track of the memory which malloc has given you, and the pointers of yours which point to it, it’s all too easy to accidentally use a pointer which points “nowhere”, with generally unpleasant results. (The basic problem is that if youassign a value to the location pointed to by a pointer:

*p = 0;

and if the pointer p points “nowhere”, well actually it can be construed to point somewhere, just not where you wanted it to, and that “somewhere” is where the 0 gets written. If the “somewhere” is memory which is in use by some other part of your program, or even worse, if the operating system has not protected itself from you and “somewhere” is in fact in use by the operating system, things could get ugly.)

11.1 Allocating Memory with malloc

[This section corresponds to parts of K&R Secs. 5.4, 5.6, 6.5, and 7.8.5]

A problem with many simple programs, including in particular little teaching programs such as we’ve been writing so far, is that they tend to use fixed-size arrays which may or may not be big enough. We have an array of 100 ints for the numbers which the user enters and wishes to find the average of–what if the user enters 101 numbers? We have an array of 100 chars which we pass to getline to receive the user’s input–what if the user types a line of 200 characters? If we’re lucky, the relevant parts of the program check how much of an array they’ve used, and print an error message or otherwise gracefully abort before overflowing the array. If we’re not so lucky, a program may sail off the end of an array, overwriting other data and behaving quite badly. In either case, the user doesn’t get his job done. How can we avoid the restrictions of fixed-size arrays?

The answers all involve the standard library function malloc. Very simply, malloc returns a pointer to n bytes of memory which we can do anything we want to with. If we didn’t want to read a line of input into a fixed-size array, we could use malloc, instead. Here’s the first step:

#include <stdlib.h> char *line; int linelen = 100; line = malloc(linelen); /* incomplete -- malloc's return value not checked */ getline(line, linelen);

malloc is declared in <stdlib.h>, so we #include that header in any program that calls malloc. A “byte” in C is, by definition, an amount of storage suitable for storing one character, so the above invocation of malloc gives us exactly as many chars as we askfor. We could illustrate the resulting pointer like this:

The 100 bytes of memory (not all of which are shown) pointed to by line are those allocated by malloc. (They are brand-new memory, conceptually a bit different from the memory which the compiler arranges to have allocated automatically for our conventional variables. The 100 boxes in the figure don’t have a name next to them, because they’re not storage for a variable we’ve declared.)

As a second example, we might have occasion to allocate a piece of memory, and to copy a string into it with strcpy:

char *p = malloc(15); /* incomplete -- malloc's return value not checked */ strcpy(p, "Hello, world!");

When copying strings, remember that all strings have a terminating \0 character. If you use strlen to count the characters in a string for you, that count will notinclude the trailing \0, so you must add one before calling malloc:

char *somestring, *copy; ... copy = malloc(strlen(somestring) + 1);  /* +1 for \0 */ /* incomplete -- malloc's return value not checked */ strcpy(copy, somestring);

What if we’re not allocating characters, but integers? If we want to allocate 100 ints, how many bytes is that? If we know how big ints are on our machine (i.e. depending on whether we’re using a 16- or 32-bit machine) we could try to compute it ourselves, but it’s much safer and more portable to let C compute it for us. C has a sizeof operator, which computes the size, in bytes, of a variable or type. It’s just what we need when calling malloc. To allocate space for 100 ints, we could call

int *ip = malloc(100 * sizeof(int));

The use of the sizeof operator tends to look like a function call, but it’s really an operator, and it does its work at compile time.

Since we can use array indexing syntax on pointers, we can treat a pointer variable after a call to malloc almost exactly as if it were an array. In particular, after the above call to malloc initializes ip to point at storage for 100 ints, we can access ip[0], ip[1], … up to ip[99]. This way, we can get the effect of an array even if we don’t know until run time how big the “array” should be. (In a later section we’ll see how we might deal with the case where we’re not even sure at the point we begin using it how big an “array” will eventually have to be.)

Our examples so far have all had a significant omission: they have not checked malloc‘s return value. Obviously, no real computer has an infinite amount of memory available, so there is no guarantee that malloc will be able to give us as much memory as we ask for. If we call malloc(100000000), or if we call malloc(10)10,000,000 times, we’re probably going to run out of memory.

When malloc is unable to allocate the requested memory, it returns a null pointer. A null pointer, remember, points definitively nowhere. It’s a “not a pointer” marker; it’s not a pointer you can use. (As we said in section 9.4, a null pointer can be used as a failure return from a function that returns pointers, and malloc is a perfect example.) Therefore, whenever you call malloc, it’s vital to check the returned pointer before using it! If you call malloc, and it returns a null pointer, and you go off and use that null pointer as if it pointed somewhere, your program probably won’t last long. Instead, a program should immediately check for a null pointer, and if it receives one, it should at the very least print an error message and exit, or perhaps figure out some way of proceeding without the memory it asked for. But it cannot go on to use the null pointer it got back from malloc in any way, because that null pointer by definition points nowhere. (“It cannot use a null pointer in any way” means that the program cannot use the * or [] operators on such a pointer value, or pass it to any function that expects a valid pointer.)

A call to malloc, with an error check, typically looks something like this:

int *ip = malloc(100 * sizeof(int)); if(ip == NULL) { printf("out of memory\n"); exit or return }

After printing the error message, this code should return to its caller, or exit from the program entirely; it cannot proceed with the code that would have used ip.

Of course, in our examples so far, we’ve still limited ourselves to “fixed size” regions of memory, because we’ve been calling malloc with fixed arguments like 10 or 100. (Our call to getline is still limited to 100-character lines, or whatever number we set the linelen variable to; our ip variable still points at only 100 ints.) However, since the sizes are now values which can in principle be determined at run-time, we’ve at least moved beyond having to recompile the program (with a bigger array) to accommodate longer lines, and with a little more work, we could arrange that the “arrays” automatically grew to be as large as required. (For example, we could write something like getline which could read the longest input line actually seen.) We’ll begin to explore this possibility in a later section.

11.2 Freeing Memory

Memory allocated with malloc lasts as long as you want it to. It does not automatically disappear when a function returns, as automatic-duration variables do, but it does not have to remain for the entire duration of your program, either. Just as you can use malloc to control exactly when and how much memory you allocate, you can also control exactly when you deallocate it.

In fact, many programs use memory on a transient basis. They allocate some memory, use it for a while, but then reach a point where they don’t need that particular piece any more. Because memory is not inexhaustible, it’s a good idea to deallocate (that is, release or free) memory you’re no longer using.

Dynamically allocated memory is deallocated with the free function. If p contains a pointer previously returned by malloc, you can call

free(p);

which will “give the memory back” to the stock of memory (sometimes called the “arena” or “pool”) from which malloc requests are satisfied. Calling free is sort of the ultimate in recycling: it costs you almost nothing, and the memory you give back is immediately usable by other parts of your program. (Theoretically, it may even be usable by other programs.)

(Freeing unused memory is a good idea, but it’s not mandatory. When your program exits, any memory which it has allocated but not freed should be automatically released. If your computer were to somehow “lose” memory just because your program forgot to free it, that would indicate a problem or deficiency in your operating system.)

Naturally, once you’ve freed some memory you must remember not to use it any more. After calling

free(p);

it is probably the case that p still points at the same memory. However, since we’ve given it back, it’s now “available,” and a later call to malloc might give that memory to some other part of your program. If the variable p is a global variable or will otherwise stick around for a while, one good way to record the fact that it’s not to be used any more would be to set it to a null pointer:

free(p); p = NULL;

Now we don’t even have the pointer to the freed memory any more, and (as long as we check to see that p is non-NULL before using it), we won’t misuse any memory via the pointer p.

When thinking about malloc, free, and dynamically-allocated memory in general, remember again the distinction between a pointer and what it points to. If you callmalloc to allocate some memory, and store the pointer which malloc gives you in a local pointer variable, what happens when the function containing the local pointer variable returns? If the local pointer variable has automatic duration (which is the default, unless the variable is declared static), it will disappear when the function returns. But for the pointer variable to disappear says nothing about the memory pointed to! That memory still exists and, as far as malloc and free are concerned, is still allocated. The only thing that has disappeared is the pointer variable you had which pointed at the allocated memory. (Furthermore, if it contained the only copy of the pointer you had, once it disappears, you’ll have no way of freeing the memory, and no way of using it, either. Using memory and freeing memory both require that you have at least one pointer to the memory!)

11.3 Reallocating Memory Blocks

Sometimes you’re not sure at first how much memory you’ll need. For example, if you need to store a series of items you read from the user, and if the only way to know how many there are is to read them until the user types some “end” signal, you’ll have no way of knowing, as you begin reading and storing the first few, how many you’ll have seen by the time you do see that “end” marker. You might want to allocate room for, say, 100 items, and if the user enters a 101st item before entering the “end” marker, you might wish for a way to say “uh, malloc, remember those 100 items I asked for? Could I change my mind and have 200 instead?”

In fact, you can do exactly this, with the realloc function. You hand realloc an old pointer (such as you received from an initial call to malloc) and a new size, and realloc does what it can to give you a chunk of memory big enough to hold the new size. For example, if we wanted the ip variable from an earlier example to point at 200 ints instead of 100, we could try calling

ip = realloc(ip, 200 * sizeof(int));

Since you always want each block of dynamically-allocated memory to be contiguous (so that you can treat it as if it were an array), you and realloc have to worry about the case where realloc can’t make the old block of memory bigger “in place,” but rather has to relocate it elsewhere in order to find enough contiguous space for the new requested size. realloc does this by returning a new pointer. If realloc was able to make the old block of memory bigger, it returns the same pointer. If realloc has to go elsewhere to get enough contiguous memory, it returns a pointer to the new memory, after copying your old data there. (In this case, after it makes the copy, it frees the old block.) Finally, if realloc can’t find enough memory to satisfy the new request at all, it returns a null pointer. Therefore, you usually don’t want to overwrite your old pointer with realloc‘s return value until you’ve tested it to make sure it’s not a null pointer. You might use code like this:

int *newp; newp = realloc(ip, 200 * sizeof(int)); if(newp != NULL) ip = newp; else { printf("out of memory\n"); /* exit or return */ /* but ip still points at 100 ints */ }

If realloc returns something other than a null pointer, it succeeded, and we set ip to what it returned. (We’ve either set ip to what it used to be or to a new pointer, but in either case, it points to where our data is now.) If realloc returns a null pointer, however, we hang on to our old pointer in ip which still points at our original 100 values.

Putting this all together, here is a piece of code which reads lines of text from the user, treats each line as an integer by calling atoi, and stores each integer in a dynamically-allocated “array”:

#define MAXLINE 100 char line[MAXLINE]; int *ip; int nalloc, nitems; nalloc = 100; ip = malloc(nalloc * sizeof(int));  /* initial allocation */ if(ip == NULL) { printf("out of memory\n"); exit(1); } nitems = 0; while(getline(line, MAXLINE) != EOF) { if(nitems >= nalloc) {  /* increase allocation */ int *newp; nalloc += 100; newp = realloc(ip, nalloc * sizeof(int)); if(newp == NULL) { printf("out of memory\n"); exit(1); } ip = newp; } ip[nitems++] = atoi(line); }

We use two different variables to keep track of the “array” pointed to by ip. nalloc is how many elements we’ve allocated, and nitems is how many of them are in use. Whenever we’re about to store another item in the “array,” if nitems >= nalloc, the old “array” is full, and it’s time to call realloc to make it bigger.

Finally, we might ask what the return type of malloc and realloc is, if they are able to return pointers to char or pointers to int or (though we haven’t seen it yet) pointers to any other type. The answer is that both of these functions are declared (in <stdlib.h>) as returning a type we haven’t seen, void * (that is, pointer tovoid). We haven’t really seen type void, either, but what’s going on here is that void * is specially defined as a “generic” pointer type, which may be used (strictly speaking, assigned to or from) any pointer type.

11.4 Pointer Safety

At the beginning of the previous chapter, we said that the hard thing about pointers is not so much manipulating them as ensuring that the memory they point to is valid. When a pointer doesn’t point where you think it does, if you inadvertently access or modify the memory it points to, you can damage other parts of your program, or (in some cases) other programs or the operating system itself!

When we use pointers to simple variables, as in section 10.1, there’s not much that can go wrong. When we use pointers into arrays, as in section 10.2, and begin moving the pointers around, we have to be more careful, to ensure that the roving pointers always stay within the bounds of the array(s). When we begin passing pointers to functions, and especially when we begin returning them from functions (as in the strstr function of section 10.4) we have to be more careful still, because the code using the pointer may be far removed from the code which owns or allocated the memory.

One particular problem concerns functions that return pointers. Where is the memory to which the returned pointer points? Is it still around by the time the function returns? The strstr function returns either a null pointer (which points definitively nowhere, and which the caller presumably checks for) or it returns a pointer which points into the input string, which the caller supplied, which is pretty safe. One thing a function must not do, however, is return a pointer to one of its own, local, automatic-duration arrays. Remember that automatic-duration variables (which includes all non-static local variables), including automatic-duration arrays, are deallocated and disappear when the function returns. If a function returns a pointer to a local array, that pointer will be invalid by the time the caller tries to use it.

Finally, when we’re doing dynamic memory allocation with malloc, realloc, and free, we have to be most careful of all. Dynamic allocation gives us a lot more flexibility in how our programs use memory, although with that flexibility comes the responsibility that we manage dynamically allocated memory carefully. The possibilities for misdirected pointers and associated mayhem are greatest in programs that make heavy use of dynamic memory allocation. You can reduce these possibilities by designing your program in such a way that it’s easy to ensure that pointers are used correctly and that memory is always allocated and deallocated correctly. (If, on the other hand, your program is designed in such a way that meeting these guarantees is a tedious nuisance, sooner or later you’ll forget or neglect to, and maintenance will be a nightmare.)