Type-stable memory management (TSM) refers to the management of
memory allocation and reclamation so that an allocated portion of
memory, a descriptor,
does not change type within some time bound 
.
This is a fancy name for an extension of an old idea.
For example, the process descriptors in many operating systems are
statically allocated at system initialization and are thus type-stable
for the lifetime of the system execution.
Our notion of TSM incorporates three basic extensions to this
conventional type
of implementation.
First, a descriptor remains a valid instance of the type even when it
is not active, i.e. on the free list.
Second, TSM allows multiple memory allocation pools for the same type.
For example, there can be a pool of thread descriptors per cluster of
processors on a large-scale multiprocessor to minimize contention
between clusters.
Finally, the type of a portion of memory can change over time,
but only as long as it is type-stable over some time 
.
More specifically, a descriptor has to be inactive for at least
before it can be reallocated as a different type
.
However, for simplicity, we assume an infinite 
for this discussion.
TSM simplifies the implementation of non-blocking synchronization algorithms. That is, because a descriptor of type T1 is type-stable, a pointer of type T1 * to the descriptor cannot end up pointing to a descriptor of another type as a result of this area of memory being freed and reallocated as type T2.
Consider, for example, the code shown in Figure 2
to do a non-blocking deletion from a linked list.
Figure 2: Deletion from the middle of list, protected by DCAS and
version number.
The delete operation searches down a linked list of descriptors to find the desired element or detect the end of the list. If the element is found, the element is atomically deleted from the list by the DCAS operation. The DCAS succeeds only if the list has not been modified since the delete operation started, as determined from the version field.
The code only checks for conflicts once it reaches the desired element or the end of the list. The descriptors are TSM so each pointer is guaranteed to point to a descriptor of this type. Without TSM, the link pointer, p, may point to a descriptor that has been deleted and reallocated as a different type. This type error can cause a random bit-field to be interpreted as a pointer, and cause the search to perform incorrectly, raise an exception due to unaligned access, or read a device register. TSM is a simpler and more efficient way of ensuring this type safety than other techniques we are aware of that prevent reallocation (such as automatic garbage collection mechanisms or reference counts), or that detect potential reallocation (such as per-list-element version numbers).
Besides these benefits to non-blocking synchronization, TSM has several important advantages in the construction of modular, reliable, high-performance operating systems. First, TSM is efficient because a type-specific memory allocator can normally allocate an instance of the type faster than a general-purpose allocator can. For example, allocation of a new thread from a free list of (fixed-size) thread descriptors is a simple dequeue operation whereas a general-purpose allocator like malloc may have to do a search and subdivision of its memory resources. The class-specific new and delete operators of C++ support a clean source code representation of TSM. This allocation can be made even more efficient with many types because a free (or inactive) descriptor is already an instance of this type, and so may require less initialization on allocation than a random portion of memory.
Second, TSM aids reliability because it is easier to audit the memory allocation, locating all the descriptors of a given type and ensuring that pointers that are supposed to point to descriptors of a given type actually do so. With fixed-size descriptors, TSM also avoids fragmentation of memory that arises with general-purpose allocators. Fragmentation can cause failure as well as poor performance. Relatedly, TSM makes it easier to regulate the impact of one type of descriptor on the overall system resources. For example, with a collection of descriptors that are allocated dynamically using the page frame approach described above, the number of pages dedicated to this type can be controlled to avoid exhausting the memory available for other uses, both from overallocation and from fragmentation of memory.
TSM also minimizes the complexity of implementing the caching model [7] of descriptors in the operating system kernel. In this approach, the number of descriptors of a given type is limited but an allocation never fails. Instead, as in a cache, a descriptor is made available by its dirty data being written back to the higher-level system management and then reused to satisfy the new allocation request. This mechanism relies on limiting the number of descriptors, being able to locate an allocated descriptor to reclaim, and being able to determine the dependencies on these descriptors. TSM simplifies the code in each of these cases.
TSM also allows a modular implementation. From an object-oriented programming standpoint, there can be a base class descriptor manager class that is specialized to each type of descriptor. For example, there is a CacheKernelObjMan class in our operating system kernel that provides the basic TSM allocation mechanism, which is specialized by C++ derivation to implement Thread, AddressSpace Kernel and MemMap types as well as several other types.