Copyright © 1999, 2004 by the authors. All rights reserved.
| Problem | Still a problem with
C++ checked pointers? |
Still a problem with
Java references? |
| 1. Difficulty reasoning about side effects due to aliasing | YES | YES |
| 2. Treating a pointer/reference as if it were an integer | NO | NO |
| 3. Treating a pointer/reference as if it were an array base | NO | NO |
| 4. Dereferencing a null pointer/reference | NO* | NO* |
| 5. Dereferencing a dangling pointer/reference | NO* | NO |
| 6. Deleting a dangling pointer/reference | NO* | NO |
| 7. Failure to reclaim storage no longer needed | NO** | NO |
* Not detected
by compiler, but detected at run-time upon occurrence
** Not detected by compiler, but usually detected at run-time upon occurrence, and reported on request
We chose to provide two different header files that a client programmer might include: one for unchecked pointers (Pointer.h) and the other for checked pointers (Pointer_CX.h). These are identical from the standpoint of a client, so it is easy to change which one is used in a client program. Effectively, the common features of these header files as seen by a client programmer are those shown below (under the name Pointer). Private members for the two different implementations, which are different, have been elided here along with the method bodies.
#ifndef POINTER_H
#define POINTER_H
#define New(p) p.Allocate (__LINE__, __FILE__)
#define Delete(p) p.Deallocate (__LINE__, __FILE__)
template <class T>
class Pointer
{
public:
Pointer<T> () {...}
~Pointer<T> () {...}
Pointer<T> (const Pointer<T>& p) {...}
Pointer<T> (void* a) {...}
Pointer<T>& operator= (const Pointer<T>& p) {...}
Pointer<T>& operator= (const void* a) {...}
bool operator== (const Pointer<T>& a) {...}
bool operator== (const void* a) {...}
bool operator!= (const Pointer<T>& a) {...}
bool operator!= (const void* a) {...}
void Allocate (long l, char* f) {...}
void Deallocate (long l, char* f) {...}
T* operator-> () {...}
T& operator* () {...}
private:
...
};
void Report_Storage_Allocation ();
#endif // POINTER_H
Problems #4, #5, and #6 are concerned with deleting and dereferencing null as well as dangling (a.k.a. "dead") pointers. As a side note, it is legal to delete null pointers in C++, so that is not an "error" we need to catch. To detect the other three cases in Pointer_CX, we need to keep track of where each pointer is pointing, and which memory locations are currently allocated. We check at run-time that a pointer points to a legal address before deleting or dereferencing it. If the check fails, execution halts and the error is reported immediately. We accomplish this by implementing a simple memory-location naming scheme along with some run-time allocation accounting (explained in the next section).
Finally, we come to problem #7: detecting storage leaks. Reference counting is used to detect most storage leaks as they happen, but of course this approach may not detect all leaks because of the possibility of circular linked structures into which the final "entry pointer" has been removed. The header file therefore declares the global operation Report_Storage_Allocation. This operation prints out the current contents of the table used to do run-time accounting in Pointer_CX (but does nothing in Pointer). A call to this operation at the end of any client program using checked pointers reports every address that was allocated but never reclaimed, along with the file name and line number of each allocation for debugging purposes. Note that a single call to Report_Storage_Allocation reports all memory allocated for pointer variables of all types. Hence, storage leaks not reported immediately upon occurrence are reported at the end of program execution.
Line (1) declares two int pointers p1 and p2. After line (3), an int has been allocated and p1 and p2 both point to it. On line (4), the int is deallocated so that p1 and p2 both become dangling references. Everything is fine so far, but line (5) becomes a potential source of problems. Typically, a new int will be allocated so that p1 will point to a legal address and p2 will still be a dangling reference. But it may turn out that the int allocated on line (5) is the same address that was just deallocated on line (4). From reasoning about the source code alone, p2 is still a dangling reference, but in this case, p2 will point to a legal address by chance! Consequently, in line (6) it is not sufficient just to check that p2 points to a legal address; we need to detect that this is an illegal deletion of a dangling reference even though p2 happens to point to a legal address on this particular run of execution.(1) Pointer<int> p1, p2;
(2) New (p1);
(3) p2 = p1;
(4) Delete (p1);
(5) New (p1);
(6) Delete (p2);
So, memory addresses alone are insufficient because the same memory location can be allocated and deallocated several times during a given execution. The key insight to solving this problem is simple: at any given point in time, every memory location is either allocated or deallocated, so we timestamp legal addresses with the unique time they were allocated. All memory is allocated with some address and at some time, so our naming scheme can use addresses for unique spatial names and timestamps for unique temporal names. The result is that the representation for a checked pointer contains two data members: a C++ pointer to the memory it points to, and a timestamp of when that address was allocated. In the case of null pointers, the value of the timestamp is meaningless.
Returning to the example above, even if the same memory address gets allocated twice, the second allocation will have a different timestamp. Consequently, we can detect in line (6) that p2 points to the right address, but at the wrong time -- that is, for the wrong allocation timestamp. Problem solved.
The last piece of machinery we need is a pointer table to store debugging information about allocated memory. Fortunately, we can use a little macro magic to gain access to the variables __LINE__ and __FILE__ defined by the C++ preprocessor. These variables indicate the line number and file name of each macro expansion. When a programmer allocates memory using New (p), the call is automatically replaced with a call to p.Allocate(__LINE__, __FILE__). In the implementation, the Allocate operation obtains the required memory and enters the address, timestamp, line number, and file name into the pointer table.
Similarly, a call to Delete (p) is automatically replaced with a call to p.Deallocate (__LINE__, __FILE__). The implementation checks whether the address and timestamp of the pointer are defined in the pointer table. If so, the memory is deallocated and the entry gets removed. Otherwise, execution stops and an error message indicates the file name and line number on which the programmer attempted to delete a dangling reference. As mentioned above, it is acceptable to delete null pointers in C++, so they are quietly ignored as a special case.
The checked pointer operators -> and * are implemented to detect illegal dereferences, including null pointers. The check is performed just as it is in Deallocate, but the resulting error messages are different. Both report that an illegal dereference has occurred, including whether it was a null or dangling pointer, and which dereference operator was used. The drawback, however, is that information about the file name and line number of the error is not available. Macros can be used to get the file and line of an operation, but the price of this information is significantly different pointer syntax. This is simply a design trade-off.
Clearly, there are several ways these key ideas can be implemented in practice. We chose to implement the accounting table by hashing pointer addresses with chaining for conflict resolution. The hash table size is, of course, a parameter that affects performance. As for the naming scheme, we implemented the timestamp mechanism by incrementing a long int variable every time an entry is made into the pointer table. This implementation is not failsafe, of course. There are approximately 4 billion unique timestamps, so eventually they may have to be reused. Our implementation will miss an error if the same address gets allocated more than once with the same timestamp and some dangling reference still points to it that later gets dereferenced or deleted. This is also a design trade-off where the risk of failure seems suitably low. Using two long int variables for timestamping would be enough to ensure centuries of execution time before any timestamps were ever reused. Alternatively, one could make system calls to the OS to get unique timestamps.