Pointers and Memory
One of the hardest topics to understand when learning to program is the use of pointers. Whilst it is a tricky subject, every programmer must learn this stuff whether you're writing VB, Java, Perl or C/C++.
Pointers work with your computer and using them correctly will make your programs much faster and let you sleep safe at night.
This article attempts to explain what pointers are, how to use them and why to use them, from the ground up. If you read this article and understand it all then good for you, a long and prosperous life awaits. If you read it and don't understand it all, don't panic - you will only suffer mild hair-loss in later life. If you don't bother to read it, you'll get hemarroids within one hour.
What Is Memory?
In order to understand pointers, you must first know what memory is since pointers can only point to memory.
Memory is a sequence of bytes, loads of them - a 128Mb machine has 134,217,728 memory locations. Each byte is accessed by a specific address, i.e. a number and consecutive memory locations are numbered consecutively.
When your program runs, it must share these locations with other programs including the operating system, device drivers etc. So for your program to access memory, it has to request it from the operating system. There are two ways to do this, the heap and the stack which are discussed later. Your program will never be given a memory location of 0 as that corresponds to an out of memory condition. The operating will always provide you with the space you asked for or an out of memory condition.
The important concept here, is that every program has its own bit of memory which it may use however it wants - storing graphics, frag limits, quadratic equations, whatever.
So, lets say we ask for 20 bytes to store a person's name, what do we get? If there are 20 bytes available to us, we'll be given a memory location N. This means that the 20 bytes from N+0 to N+19 are ours to do with what we want. Check out my groovy diagramming skills below:
The diagram shows the 20 bytes we requested as black squares whilst the rest of the memory - which we are not allowed to read or write is shown in red.
So that covers, the basics of memory. More advanced technical stuff is covered in the section on memory paging later in the document.
What are Pointers?
A pointer is a sequence of memory locations that contain a memory address. In those languages that support pointers (C, C++, Pascal etc), the pointer is just a variable. In languages that lack pointer support (Java, Perl etc), the pointer still exists but it is hidden from the programmer by the run-time environment.
So, if we expand the diagram from the previous section to include our new pointer P, it will look like this:
Our pointer location, P now points to memory location N - the start of the memory block we allocated in the previous section. Note that I have chosen to represent P with four bytes (four black squares), this is means that our pointers are 32-bits size (as are most machines today).
Diagrams like the one above are the best way to visualise what is going on in memory with pointers and allocated memory. If you hit a tricky problem when programming with pointers, get a piece of graph paper and draw what you think is going on in memory to help work through the problem.
The Heap and the Stack
There are two ways in which a program can get its hands on memory - from the heap or from the stack. The heap is an area of memory from which the program can explicitly request memory using functions like new() and malloc(). The program has access to that memory until it explictly releases it by calling delete() or free(). A program which gets memory from the heap but which doesn't bother to deallocate it, is said to have memory leaks.
Memory allocation and deallocation from the stack is handled automatically by the compiler. Whenever a function is called, its parameters are allocated from the stack without the programmer needing to perform any extra work. When the function exits, the parameters are automatically deallocated. Similarly, local variables are allocated from the stack and deallocated when they go out of scope.
The stack works in a last in, first out (LIFO) manner because the last thing allocated from the stack is always the first thing to be deallocated. Because of this, memory allocation from the stack is much faster than using the heap.
The stack can cause further problems for developers working with pointers because memory is automatically deallocated. If a function returns a pointer to a local (automatic) variable, that variable will be deallocated when the function exits and the pointer will now point to invalid memory.
Word Boundaries
Variables of the common, built in types have different sizes, characters are usually 1 byte, integers often 4 bytes (32 bit) whilst doubles are 8 bytes. The computer's CPU is designed with this in mind and its built in instructions are implemented to make use of the fact. This means that, for example, a CPU instruction to move a 32 bit integer in memory is significantly more efficient when the integer is stored on a 32 bit boundary - i.e. its memory address is divisible by four.
So what are the consequences of this? Well, this is important when you're working with bits & bytes. Imagine you have a serial device which will handle a message consisting of an 8 bit command identifier followed by a 32 bit data item. An engineer who had never heard of word alignment would write the following C code to describe the message:
typedef struct SDeviceMsg {
unsigned char m_ucCmdID;
unsigned int m_uiDataItem;
};
.
.
.
SDeviceMsg msg = { 1, 2 };
SendToSerialPort(&msg);
The author thinks that he/she can take the address of an SDeviceMsg structure and expect an 8 bit value followed immediately by a 32 bit value - a total size of 5 bytes. "But!", the smart cookie reader exclaims, "What about word alignment, that code will crash and burn like a dog. Ha, ha, ha, haaaaaaa!".
The smart cookie reader is correct, but there's no need for such maniacal cackling. The 32 bit value, m_uiDataItem, must be aligned on a 4 byte boundary but the unsigned char, m_ucCmdID, need only be aligned against a single byte. The structure size is in fact 8 bytes:
- 1 byte - m_ucCmdID
- 3 bytes - padding to ensure that the address of the following value is divisible by 4
- 4 bytes - m_uiDataItem
It should be noted that the start of all allocated structures is aligned with the largest type supported by the CPU - usually the double weighing in at a hefty 8 bytes. This is because functions like malloc() allocate raw memory which is then cast to the desired type. So the results of the following malloc() are always aligned on a 8 byte boundary, otherwise dereferencing pD would result in unaligned data:
double *pD = (double *)malloc(sizeof(double));
Many CPU's will cope if data is not aligned. Sun machines will do this without a whimper, DEC UNIX machines print a warning message on stderr but HPUX machines fire a bus error which often corrupts the stack also. So if you are writing portable code, you should always respect the need for word alignment or suffer the consequences.
Memory Paging
Operating systems that make use of virtual memory, provide memory to a process in a series of pages. Pages can then be swapped to and from the hard disk as they are needed. A memory page need not always be loaded into the same portion of physical RAM each time it is restored from disk - this means that your pointers do not contain physical memory addresses, they store a page identifier and an offset.
What Happens When You Make A Mistake With Pointers
There are great many nasty things that can happen when you get pointers wrong, your dog could die, spouse walk out on you and children grow up to be politicians, but on UNIX, the most common are as follows:
Segmentation Violation
You are attempting to access memory which does not belong to you. A segmentation violation results in a signal which causes a core dump. Do not attempt to ignore the signal, your underpants will catch fire.Bus Error
This error occurrs when you attempt to access memory which physically does not exist or use unaligned memory. Note that many systems no longer produce this error when you access memory which physically does not exist due to the advent of memory paging, they produce a segmentation violation instead.Invalid Instruction
Oh dear this is a bad one. The program counter is probably pointing to data area and attempting execute your data as machine instructions. This is usually due to the stack having become corrupt previously in the program.Generally Bizarre Behaviour
Not all pointer boo-boos are caught by the operating system as the OS can only detect when you read or write memory which you don't own. You could allocate an array of 12 bytes for one variable then allocate space for a 4 byte variable (both on the stack), if you write 14 bytes into your 12 byte array you will have trashed 2 bytes of the 2nd variable but not caused an OS error.
The first two types of problem are the most common and can usually be detected an fixed with the help of a good debugger, but the last two are much more difficult to correct. To help you, there are a number of great tools on the market such as Rational's Purify and Numega's Bounds Checker. These tools add extra instructions to your executable to find nasty errors as they happen. Some debuggers even attempt to perform similar checks but they are nowhere near as effective.
Pointer Terminilogy
This section introduces some common pointer related terms and explains what is really mean by all those big words:
Pointer Arithmetic
The art of adding, subtracting and sometimes even multiplying pointers, in the example above, if we know that the surname of our person is 10 bytes into our memory block, then we can set a new pointer P2 = N+2 to point to the surname using pointer arithmetic. Use extreme caution when applying such techniques and always keep a pointer at the start of any memory that you allocate.Loose Pointers
A pointer which does not point to any useful memory. An occurrence usually precedes a spectacular crash involving much swearing.NULL Pointer
A pointer which does not point to any useful memory but which has been set to point to memory address 0 (zero). Careful programmers can then check whether a pointer is NULL before they use it, the rest of us wait for the crash and then start swearing.Memory Leak
Memory which requested from the heap by the program but which is never released. This is a bad thing.Virtual Memory
Using a hard disk to store memory pages in order to allow programs to make use of more memory than is physically installed on your machine.
