Chapter 4: Dynamic Allocation and Deallocation of Memory

Overview

Fundamentals of dynamic allocation and deallocation of memory: free store (system heap); per-process memory manager; C memory allocators malloc() , calloc () , and realloc() ; and C deallocator free() .How to handle memory allocation/deallocation errors.

In previous chapters we have mentioned dynamic allocation of memory several times. In Chapter 2 we had quite a detailed look at the static allocation when we discussed the process of compilation, linking, loading, and execution of a program. We mentioned dynamic allocation from a general point of view or, to be more precise, from the operating system point of view.

The reader should be comfortable with the idea that a running program is allocated several segments - not necessarily contiguous - of memory to which its address space is mapped during program execution. These segments together constitute "the program's memory space", or the "memory it owns", where all the program's instructions and data needed for the execution are stored and accessible. It is obvious that many programs need to increase their memory during their execution; for instance, they might need to store more data or even more instructions.

As mentioned at the end of Chapter 2, it would be more precise to talk about a process rather than a running program. Modern operating systems like UNIX thus have a process memory manager, software that is responsible for providing additional allocation of memory to its process and for deallocation when the memory is no longer needed. Since it is not our aim to discuss operating system issues (unless they are directly related to programming in C/C++), suffice it to say that memory management on the operating system level is usually a two- tier affair (see Figure 4.1): first an operating system memory manager allocates rather large "chunks" of memory to individual process memory managers and also keeps track of them. Then each process memory manager allocates smaller " chunks " of the memory to its process and keeps track of allocated and free segments: when its process requests deallocation of a segment, it puts that segment on the list of free segments; if running out of memory, it requests another big chunk from the operating system memory manager.

Figure 4.1: Two-tier memory management

But what does it really mean to "allocate a segment of memory"? In essence, memory management is a very simple "accounting" of what process owns what part(s) of the memory. (The reader must forgive us this oversimplification, but as stated previously we do not want to be sidetracked by operating system issues not pertinent to C/C++ programming concepts.) Thus, memory allocation is nothing more or less than making an entry in the "accounting book" that this segment is given to this process for keeps, and memory deallocation is an entry that this segment is not needed by this process and hence is "free". Obviously, decisions concerning which segment to allocate, how to make sure that the fragmentation (subdividing bigger segments into smaller ones) does not degrade performance, and many other issues are rather important and complex to solve. However, the programmer must seek to understand the concepts of allocation and deallocation of memory and so need not bother with such technical issues.

It is clear that we are interested in the process memory manager: what is happening (and how) when our program requests more memory or returns some memory no longer needed. It is actually more efficient not to have the process manager "return" freed memory segments to the operating system memory manager; thus both allocated and freed memory segments remained assigned to the process. The freed segments are kept by the process memory manager for serving future requests and possibly for unifying adjacent segments into bigger ones (to partially alleviate the fragmentation caused by previous allocations ). This may be surprising to some programmers because, with most operating systems, frequent checks of memory usage while a program is running will show that it never decreases (in LINUX it seems to decrease, but this is caused by the way memory use is reported rather than by segments being returned to the operating system). This does not necessarily mean that the program is suffering memory leaks. Normally, memory usage should reach a certain steady state as either no new memory is requested or the requests can be served by using the freed segments. Only if memory usage keeps growing and growing do we face the ignominious memory leakage.

The operating system process manager usually keeps track of allocated blocks in a data structure called the binary heap (a binary tree in which each node is labeled by a label that is smaller than labels of all its descendants), whose purpose is to facilitate fast and efficient searching for a suitable free block. This heap is sometimes referred to as the system heap or free store. The process memory manager usually keeps a dynamic list of free segments. One implication is that, every time your program requests more memory, the process memory manager must search through the list to find a suitable segment; if none is found, more memory must be requested from the operating system memory manager, which must search the system heap for a suitable block. After delivery to the process memory manager, a suitable segment must be carved out from the freshly allocated block. It is therefore impossible to estimate how long it will take to execute a memory allocation request. Even though modern computers and operating systems are very fast, if our program performs a significant number of allocations and deallocations then the attendant yet unpredictable delays may affect the program's performance. These issues must be considered for real-time software systems and for all programs where performance is essential. We will look at these issues when we discuss the concept of "allocation from arena" in Chapter 9.

In modern operating systems, the operating system manager is not a part of the process code but instead is engaged by a system call from the process. The appropriate system call is thus particular to each operating system and each hardware platform. It is desirable and practical to shield an applications programmer from such idiosyncrasies, so C/C++ compilers come equipped with standard functions that provide OS- and platform-independent interfaces to the appropriate system calls. These C standard functions are malloc() , calloc() , realloc() , and free() (the appropriate prototypes and other relevant definitions can be found in the slightly obsolete header file malloc.h or in the more up-to-date header file stdlib.h ); even though these C functions can be used without penalty in C++ programs, more sophisticated versions of these are the C++ operators new , new[] , delete , and delete[] , and programmers are strongly encouraged to use them. In this chapter we focus on the "plain" C functions; we will discuss specific issues pertinent to the C++ operators in Chapter 8. From now on we may consider (albeit somewhat imprecisely) these functions as programming interfaces to the process memory manager.

The synopsis (function prototype together with the necessary header files) of malloc() is rather simple:

 #include <stdlib.h>    void *malloc(size_t size); 

The argument size is the size of memory requested in bytes; malloc() either returns NULL if unsuccessful or returns the address ( void* is just a plain address) of the beginning of the allocated segment. The segment allocated is properly aligned. Note that malloc() can fail for any of three reasons: if there is not enough memory left for allocation (the free store is depleted); if the size requested exceeds the limit allowed for allocation; or if the process memory manager has somehow been corrupted.

Let us state that we do not really need this previously unmentioned data type size_t , since it is just the good old unsigned long in disguise. However, it is defined according to ANSI-C standard to provide for more careful type checking.

It might come as a surprise to some, but malloc() may in fact allocate a bigger segment than requested. You are guaranteed to receive at least as many bytes you have requested, but you may also get more. The reasons concern both the way malloc() works and the way memory and access to it are organized. From the programmer's point of view it should not matter, for we can never be certain how many bytes were in fact allocated to us; thus, we can only count on the number of bytes we requested. This note's sole purpose is to put some programmers at ease when they check their running program and notice that the memory allocated is more than what the program is asking for (i.e., this is not necessarily symptomatic of a memory leak).

Let us repeat once again that memory can never be "empty". What, then, are the contents of a malloc() allocated segment? A common error is to assume that it is blanked (or cleared ) when all its bits are set to 0. Even though it often happens this way (depending on where the segment is drawn from), in fact the contents of the segment are arbitrary and hence meaningless. Thus, the contents of a segment allocated by malloc() should not be used until it is set by the program to hold some meaningful value or values.

Besides assuming that the contents of a malloc() allocated segment are somehow set, another common error is allocating an insufficient number of bytes, which results in overflow when storing value(s) requiring more bytes. The reader is encouraged to refer to Chapter 3 for more detailed discussion of this topic.

The synopsis of calloc() is as simple as that of malloc() :

 #include <stdlib.h>    void *calloc(size_t nelem, size_t elsize); 

Whatever has been said for malloc() applies also to calloc() , except that calloc() blanks (clears) the allocated segment and that the number of bytes allocated is nelem*elsize (in simple words, we are asking calloc() to allocate enough bytes for nelem elements of size elsize ).

The synopsis of realloc() is also simple:

 #include <stdlib.h>    void *realloc(void *ptr, size_t size); 

though its semantics is more complex and its use is rather controversial .

Let us first address the semantics of realloc() . It is designed to expand or reduce an already allocated segment. The role of the argument ptr is exactly that - it is a pointer to the segment that we want to expand or reduce, while size stipulates the size in bytes of the expanded or reduced segment (which we will refer to as new size ; we use old size when referring to the size of the segment prior to the call to realloc() ). A null value of ptr is interpreted as there being no segment yet to expand or reduce, and then realloc() behaves like malloc() .If size is 0, then realloc() works like free() and the segment is deallocated. Note that realloc() guarantees the contents of the segment to be unchanged (up to the smaller of the old size and the new size).

All that has been said so far about realloc() is rather straightforward and plausible, so where is the controversy mentioned earlier? First, unless ptr points to a segment previously allocated via malloc() , calloc() , or realloc() , unpredictable problems may occur - including corruption of the process memory manager. Second, though it is not a problem to reduce a segment, it may be a problem to expand it. If there is not enough memory available to the right of the segment's end, then realloc() creates a new segment of the extended size somewhere else in the memory, copies the contents of the old segment up to the old size to the new segment, frees the old segment (see our discussion of free() that follows ), and returns the pointer to the new segment. In essence, while the old segment is being extended, it may or may not move in the memory. For many purposes it does not matter that the extended segment has moved, but any meaningful links to the old segment in the program become dangling pointers, with all the consequences discussed in Chapter 3.

Let us illustrate this problem on a small example that is actually quite common. Assume that a program works with a binary tree, a fragment of which is depicted in Figure 4.2. Let us further assume that the program needs to extend the node c and does so using realloc() . Consider the situation when the expanded node (segment) did not move, depicted in Figure 4.3. The fragment of the tree (and hence the whole tree) is sound.

Figure 4.2: Fragment of a binary tree

Figure 4.3: Node c was extended but has not moved

Now consider the situation depicted in Figure 4.4, where the node (segment) moves while it is extended. The fragment of the tree is no longer sound; in fact, it is no longer a tree because the right child link of the node a is dangling.

Figure 4.4: Node c was extended and has moved

It is no accident that the modern and better-designed memory allocators of C++ ( new and new[] ) have no counterpart to realloc() . It is always safer to manage such situations through an explicit allocation of a new segment, an explicit update of all links pointing to the old segment so that they point to the new segment, an explicit copying of all data from the old to the new segment, and finally an explicit deallocation of the old segment.

The previous paragraphs have covered the fundamentals of dynamic memory allocation in C. We are left with the task of returning the unneeded memory by a program to its process memory manager, or memory deallocation. This is the role of the C deallocator free() , whose synopsis is:

 #include <stdlib.h>    void free(void *ptr); 

The function free() inserts the segment pointed to by ptr back into the list of free segments kept by the process memory manager. As with the realloc() function, ptr must point to a segment previously allocated via malloc() , calloc() ,or realloc() . Otherwise, unpredictable problems may result, which could even include corrupting the process memory manager. If the value of ptr is NULL , no action takes place.

Throughout this chapter, we have mentioned the errors that can arise during dynamic memory allocation and deallocation. Let us briefly summarize these errors and suggest how to treat them. Note that the C functions we have discussed do not have any error handling mechanisms (such as "exceptions" in C++), so it is up to the programmer to decide how the errors should be dealt with programmatically.

Allocation (using malloc() , calloc() ,or realloc() in allocation mode) can fail for three reasons only: (i) not enough memory; (ii) asking for a bigger segment than the limit allows; or (iii) some kind of corruption of the data kept by the process memory manager. We therefore suggest immediate program termination in the event of a memory allocation failure. Of course, the termination should provide the user with a report that is as detailed and localized as possible (the most appropriate form is through logging, discussed in Chapter 10) so that the nature of the error can easily be determined if necessary.

Of course, such an approach cannot be used for safety-critical and/or fault-tolerant software. Such software should be designed differently - for instance:

• the dynamic memory allocation should be done prior to the execution of the critical section of the program, so a crash would not cause severe problems;

• the program should obtain as much dynamic memory as possible at the beginning and then use its own memory manager to manage it (we will discuss this together with "allocation from arena" in Chapter 9); or

• the program should have the ability to build the most important dynamic data structures it needs and work with them on disk in a special "error mode" - although this degrades performance, it nevertheless allows execution of the critical section to continue (even though in most cases the virtual memory system of the operating system does exactly that).

Reallocation (using realloc() in reallocation mode) may fail for the additional reason that the pointer of the segment to be reallocated is incorrect. Unlike allocation errors, which do not usually indicate a badly designed program, a reallocation failure is usually a programming error and as such should be discovered and treated during testing and debugging. A debugging version of realloc() should be able to check if the pointer value is correct (i.e., previously allocated) and, if not, allow for detailed debugging (see Chapter 10).

Similarly, free() should only be checked in the testing and debugging phase, and only for the purpose of preventing memory leaks (see Chapter 10). A debugging version of free() should work along the same lines as indicated for realloc() .

Errors caused by improper use of allocated and/or deallocated memory were covered in Chapter 3.

It is clear that different versions of these functions, including custom-made ones, can be used instead of the standard versions. There are many such replacements available, providing either faster and more efficient allocation/deallocation or additional features (such as debugging or reporting). We will discuss this further in Chapter 10.