Tombstone (programming)
Encyclopedia
Tombstones are a mechanism to detect dangling pointer
s that can appear in certain computer programming language
s, e. g. C
, C++
and assembly language
s, and to act as a containment to their dangerous effects.
A tombstone is a structure that acts as an intermediary between a pointer and the heap-dynamic data in memory. The pointer – sometimes called the handle
– points only at tombstones and never to the memory that holds the actual value. When the data is deallocated, the tombstone is set to a null (or, more generally, to a value that is illegal for a pointer in the given runtime environment), indicating that the variable no longer exists. This prevents the use of invalid pointers, which would otherwise access the memory area that once belonged to the now deallocated variable, although it may already contain other data, in turn leading to corruption of in-memory data. Depending on the operating system
, the CPU
can automatically detect such an invalid access (e. g. for the null value: a null pointer dereference error). This supports in analyzing the actual reason, a programming error, in debugging
, and it can also be used to abort the program in production use, to prevent it from continuing with invalid data structures.
In more generalized terms, a tombstone can be understood as a marker for "this data is no longer here". For example in filesystems it may be efficient when deleting files to mark them as "dead" instead of immediately reclaiming all their data blocks.
The downsides of using tombstones include a computational overhead
and additional memory consumption: extra processing is necessary to follow the path from the pointer to data through the tombstone, and extra memory is necessary to retain tombstones for every pointer throughout the program. One other problem is that all the code – that needs to work with the pointers in question – needs to be implemented to use the tombstone mechanism.
No popular programming language currently uses tombstones. However, built–in support by the programming language or the compiler is not necessary to use them.
Dangling pointer
Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations....
s that can appear in certain computer programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s, e. g. C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
and assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
s, and to act as a containment to their dangerous effects.
A tombstone is a structure that acts as an intermediary between a pointer and the heap-dynamic data in memory. The pointer – sometimes called the handle
Handle (computing)
In computer programming, a handle is a particular kind of smart pointer. Handles are used when application software references blocks of memory or objects managed by another system, such as a database or an operating system....
– points only at tombstones and never to the memory that holds the actual value. When the data is deallocated, the tombstone is set to a null (or, more generally, to a value that is illegal for a pointer in the given runtime environment), indicating that the variable no longer exists. This prevents the use of invalid pointers, which would otherwise access the memory area that once belonged to the now deallocated variable, although it may already contain other data, in turn leading to corruption of in-memory data. Depending on the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
, the CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
can automatically detect such an invalid access (e. g. for the null value: a null pointer dereference error). This supports in analyzing the actual reason, a programming error, in debugging
Debugging
Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware, thus making it behave as expected. Debugging tends to be harder when various subsystems are tightly coupled, as changes in one may cause bugs to emerge...
, and it can also be used to abort the program in production use, to prevent it from continuing with invalid data structures.
In more generalized terms, a tombstone can be understood as a marker for "this data is no longer here". For example in filesystems it may be efficient when deleting files to mark them as "dead" instead of immediately reclaiming all their data blocks.
The downsides of using tombstones include a computational overhead
Computational overhead
In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal...
and additional memory consumption: extra processing is necessary to follow the path from the pointer to data through the tombstone, and extra memory is necessary to retain tombstones for every pointer throughout the program. One other problem is that all the code – that needs to work with the pointers in question – needs to be implemented to use the tombstone mechanism.
No popular programming language currently uses tombstones. However, built–in support by the programming language or the compiler is not necessary to use them.
External links
- Safe-C programming language (implements safe pointers using Tombstones)