All of this section is hard
All of this section is hard
C variables can be stored in one of two places: the stack and the heap. They can also have their addresses resolved by the linker or by the compiler. Which of these options are chosen has a bearing on their behaviour when the C program is running
Dynamic memory allocation is a very powerful tool for building complex data structures of arbitrary size. As with many powerful constructs, it is possible to introduce subtle and elusive bugs into programs which use them. However, using pointers and structures to implement dynamic data structures makes for very efficient programs.
So far, all example programs have relied on automatic variables. These variables are declared at the beginning of a compound statement or as formal parameters of functions. Memory is reserved for variables thus defined which disappears automatically on ending the current context. Consequently, there is no risk of memory leaks occurring because the memory occupied by the variable is returned to the system as soon as execution passes outside the compound statement or the function returns.
To understand how memory for function parameters and automatic variables is allocated, it is necessary to know a little about machine architecture. All modern microprocessors contain hardware support for a structure referred to as a stack.
The stack is a last-in-first-out (LIFO) queue. This means that data is "pushed onto" the stack in a particular order, then retrieved ("popped") in reverse order. In most processors, the stack starts at a high memory address and grows downwards as more information is added.
The processor maintains a stack pointer internally. As data is pushed onto the stack, the stack pointer is automatically decremented; as it is popped from the stack it is automatically incremented. The following short example shows what happens when a function is called. The exact history of the stack and the stack pointer is dependent upon which architecture is executing the program (for example, in some processors, the stack pointer points at the first free stack element rather than the last used one), but the order of events is always the same.
As well as reserving local memory simply by declaring variables, it is possible to ask the system for some memory in the stack as the program is running. The advantage of this is that it now becomes possible to make an automatic variable, for example, of a size which is not known at compile time. C allows arrays to be declared in the normal way if the size is a constant (one writes int a[10];, for example), but it is not permitted to write int a[i]; where i is a value which can only be determined as the program runs. Such an array would be said to be allocated dynamically because the reservation of memory does not occur until the program is running. However, it is possible to ask for a pointer to a given amount of memory from the stack using the alloca (allocate automatic) function as follows:
This code allocates enough memory to store i integers, then sets a to point at it. a can now be used just as if it were an array declared normally, but its size did not have to be known until the program ran. If the allocation fails, for example because the system has insufficient resources to satisfy the request, alloca returns NULL, the program prints a message on the standard error stream and exits with an error code (in this case, -1).
There is one caveat. Although alloca has appeared in early versions of BSD Unix and was documented in BSD4.2, it has not made it into the POSIX standard. Although it is widely supported on almost all platforms, for absolute portability it would be best to avoid its use. In particular, some Microsoft(TM) compilers have trouble with it, although it is available and reliable on programs written for the Windows platform using the gcc C compiler.
Fortunately, the stack is not the only place where memory can be reserved at run time. Read on...
We have seen that variables which are declared at the top of the C source files are global, i.e. accessible throughout the program, provided that they are declared external where used in other source files. Such variables are allocated space in the heap at compile-time.
In fact, there are two more places where declared values can be stored. Strings which are declared as constants using double quotes "thus", and global variables which are declared const are placed at the bottom (usually) of the heap in an area of memory which is marked as read only, so that any attempt by the program to modify it causes a segmentation fault. Global variables (i.e. not constants) are allocated space in the main part of the heap.
Variables stored in the heap persist until program termination. Just as alloca reserves space for automatic data at run time, the malloc, calloc and realloc subroutines are available to programmers wishing to reserve space on the heap (see Dynamic Allocation). Because, unlike automatic data, data stored using malloc etc persists, it is vitally important to return memory obtained with malloc or calloc to the system when it is no longer required. Failure to do so results in an ever increasing usage of heap resource until eventually the program fails because system memory is exhausted. This is referred to as a memory leak and is often responsible for the most elusive bugs, because the program may collapse from exhaustion in a place completely unrelated to the origin of the bug.
Almost all variables seen in C programs are automatic ones that are stored on the stack. The keyword auto has more or less become obsolete, and is retained only for compatibility with very old source code (it is assumed by default for all variables defined inside compound statements, and isn't allowed anyway outside this context).
However, sometimes it is helpful to be able to declare a variable within the scope of a particular block which isn't stored on the stack. This kind of variable isn't accessible outside the current scope, and is persistent: its value is retained when the variable falls out of scope the for the next time it is back in scope. Consider the following function:
The local variables inside reptVar in the above example are declared static, so the values are set once at load-time, and are retained across function calls. If the variables were auto (the default), the initialisation would take place each time the function was called, and the parameter would be returned each time. Since the variables are declared static and their value is retained, the function behaves very differently: it "learns" the value of the parameter the first time it is called, then repeats that number on every subsequent call, regardless of the parameter which is actually supplied.
Creating variables which are "remembered" across function calls is the main reason to use the keyword static, but what it actually means to the compiler is "store this variable in the static data segment and resolve references to it at compile time". The main consequence of this, as explained above, is that such variables are not stored on the stack, and that the variables' values are retained across calls as previously described.
Another consequence of declaring a variable static applies to those declared at the start of the file before any other code. It is that, because it is the compiler's job to resolve the address instead of the linker's, the variable becomes totally invisible to other C program source files which can no longer use it even by declaring it extern. It is therefore possible to declare variables which are "global" to the C file, and not to the whole program. This is rather similar to the idea of declaring variables as "private" in some other languages, and is useful in larger programs where it is important to keep the number of genuinely global variables to an absolute minimum in order to keep the program maintainable and reduce the likelihood of errors.
Declaring functions to be static similarly hides them from being called from outside the current C file, and is another useful trick for maintaining the reliability and maintainability of larger programs.
Memory on the heap can be reserved for use in your program using the malloc or calloc. malloc takes a single argument of type size_t which on most systems is synonymous with an unsigned long integer. It allocates memory on the heap and returns a pointer of type void * to the area it has reserved. If there is no memory left to reserve, or some other problem occurs, it returns NULL. The memory isn't initialised in any way. calloc takes two arguments, both of type size_t: the first is the number of things the program needs to be able to store in the memory, and the second is the size of each thing. The memory returned is filled with zeros.
Having obtained some memory from the system, the pointer has to be cast to the correct type before it is used. This is inevitable, because there is no way that malloc or calloc can know the use to which the memory is going to be put. Consequently, lines of the form shown on the left of the panel below are commonplace.
typedef struct myStruct MyStruct;
MyStruct *ms = (MyStruct *)
malloc(sizeof(MyStruct));
struct myStruct *ms =
(struct myStruct *)
malloc(sizeof(struct myStruct));
This is a bit of a mouthful, but just means "allocate memory equal to the size of a struct myStruct, convert the resulting pointer to point to an entity of that type, and use that as the initial value of the declared pointer variable."
Using the keyword typedef greatly helps to reduce the verbosity of this procedure. The programmer can define a new type, in this case MyStruct which is synonymous with a struct myStruct. Note the change in case. It is common practice for programmers to adopt a particular style in naming variables (for example choosing between _ or mixed case -- my_struct or myStruct -- for simple variables, and using names beginning with upper case for structure names and new types). If modifying someone else's program it is confusing and discourteous not to adopt their naming convention. It is also possible to declare new pointer types: for example, typedef struct myStruct *MyStructPtr; declares a new type which is a pointer to a struct myStruct.
typedef is exactly the mechanism used to create the type FILE which is used by standard input and output functions.
Care must be taken not to forget the memory allocated from the heap. Storage thus allocated is anonymous: the only way you can get at it is by storing the pointer returned from the allocation function. Look at the following example:
At the end of the example, the program's data is still stored somewhere on the heap, but has become inaccessible. Perhaps the program has no further use for it: this is OK, but in that case the programmer should have written free(mem) at some time before line 3 in order to return the memory used to store the three integers to the system. By not doing so, a memory leak has been created.
If the programmer's intention was to increase the size of storage from three ints to five, the right way to do it is to call realloc. This function takes two arguments: the first is the pointer to an existing area of memory which has been obtained via a call to malloc or calloc; the second is the new size in bytes. realloc returns the pointer to the memory block of the new size, or NULL if the request cannot be satisfied. The new memory block contains the same data as the old (or part of it if the size was reduced). Line three above might have been written mem = (int *)realloc(mem, 5*sizeof(int)); the first three integers would have been retained, but two "new" integers would have undefined values.
Losing the address of reserved memory is a very common bug, and can be heavily disguised. In fact, it is such a frequent cause of bugs that some modern languages automate the allocation and freeing of heap memory completely. The Java run-time, for example, has no equivalent of the free subroutine: instead, the run-time periodically performs a process called garbage collection to remove unreferenced data from the heap. This makes programs a lot easier to write, but imposes an extra run-time overhead. Furthermore, it is possible to "fool" the garbage collector under some circumstances (although only under rather bizarre ones thanks to recent research results in garbage collection) so that the absence of memory leaks can still not be totally guaranteed.
A more serious consequence of automatic garbage collection, especially for embedded systems which are likely to be running hard real-time applications, is that one never knows exactly when the garbage collection is going to happen. Since garbage collection is a computationally non-trivial process, this could result in the machines performance being compromised for a short time while it takes place. Sod's law indicates that the garbage collector will engage just before a period of maximum system activity.
As well as allocating and freeing memory, the ISO 9899 standard defines the behaviour of other memory management subroutines which have their prototype in string.h. The following are précis of the GNU manual pages which describe them.
| void *memccpy(void *dest, const void *src, int c, size_t n); | Copies no more than n bytes from memory area src to memory area dest, stopping when the character c is found. |
|---|---|
| void *memcpy(void *dest, const void *src, size_t n); | Copy at most n bytes from src to dest. The areas of memory may not overlap. |
| void *memmove(void *dest, const void *src, size_t n); | As memcpy, but the source and destination memory areas may overlap. |
| char *strcpy(char *dest, const char *src); | Copy a string including the terminating '\0' character from src to dest. Since no check is made to ensure the string will fit in the destination area, it is usually unsafe to use this function and strncpy should be preferred. |
| char *strncpy(char *dest, const char *src, size_t n); | As strcpy, but do not copy more than n bytes. This might mean the terminating null is not copied, and that the result is not a valid string, but at least no other variables are corrupted. |
Using malloc, calloc, realloc and free, it is quite clear how to solve problems that require arrays of a size unknown at compile time, or with a size that needs to vary as the program continues. However, by combining dynamic memory allocation with structures and pointers, it is possible to create even more flexible types of data structure.
One of the simpler examples of such a structure is a linked list. This consists of a pointer to the head of the list, which is composed of zero or more structs. Each structure contains some data, and a pointer to the next structure in the list. In some applications, there is merit in maintaining a pointer to the tail of this list as well as the head: for example, if all additions of the list are going to occur at the tail rather than be inserted somewhere in the list. Such a data structure is referred to as a singly-linked list, and an example is shown at the top of the panel on the left.
Alternatively, the structs contain pointers to the previous element in the list as well as the previous one, resulting in a doubly-linked list as shown in the centre of the diagram on the left. This is useful if, for example, data in a sorted list has to be traversed in both ascending and descending orders.
More complex data structures which may be implemented using structures containing pointers, such as binary trees.
As an example of linked list usage, consider the construction of a linked list containing integer values which are to be added in ascending order. As it will be necessary to read down the list to determine the insertion point, the tail pointer won't be required. This source code is from the file list.c
Automatic variables are stored on the stack and consequently disappear when they go out of scope. Variables stored on the heap are persistent, and care must be taken to free memory allocated to store them so as not to cause memory leaks.
Static variables and functions have their addresses resolved at compiler time, and are therefore only visible within the current C file. Static variables are persistent.
Using dynamic data structures by using structures containing pointers, and allocating memory with calloc, malloc or realloc, arbitrarily complex data types can be constructed.
The tools upon which this course relies are Copyright the Free Software Foundataion where they are made available under the GPL (GNU Public Licence).
The content of this course was derived from that generated by many ex-colleagues at the University of Leeds, Department of Electronics and Electrical Engineering. Much of the content has been reworked, and substantially augmented, but Dr N J Bailey, Centre for Music Technology, The University of Glagsow. This manifestation is Copyright N J Bailey; some of the content is Copyright The University of Leeds.
Diagrams on this resource are drawn in XFig and are rendered by the browser using The University of Hamburg's Simple FIG viewer applet which is Copyright (C) 1996-2002 F.N.Hendrich, hendrich@informatik.uni-hamburg.de.
The source code, programming examples and exercises are all specific to this course, and are Copyright, Dr N J Bailey.
The applet for viewing and demonstrating C programs is Copyright Dr N J Bailey, and is to be found documented and with its source code on the Centre for Music Technology website under Software