The Standard Librarian: a Debugging Allocator
Matt austern
Http://www.cuj.com/experts/1912/AUSTERN.HTM?topic=Experts
-------------------------------------------------- ------------------------------
Allocator in the C standard library has a complex and low-level interface [Note 1]. Unlike New Delete, they decouple memory allocation with object constructors. Unlike Malloc and Free, they require you to be confirmed by the number of data types and objects of memory.
Usually, this is not a problem. Allocator has a low-level interface because they are low-level concepts: they are typically hidden inside the container class, rather than the code of ordinary users. However, sometimes you may have to care about Allocator: When you write a new container class. Allocator is more difficult than New / Delete, so it is easier to happen. If you write the code to use allocator, how to ensure that the code is correct? The testing of the runtime cannot be proved that there is no error, and only the wrong existence is proved. Despite this, the test is still very important - the sooner you discover BUG, the sooner it will be corrected.
All standard container classes accept an Allocator class as their template parameters; this parameter has a default value, such as std :: Vector
This article will show such a Debugging Allocator class. It is valuable in its applicable range and implements it is also an interesting practice using allocator.
test
What kind of incorrect do we want to check? the most important is:
l The memory delivered to DEAllocate () is indeed this allocator assignment.
l When deallocate () is included, the number of bytes as the assignment is returned. (Unlike Malloc and Free, Allocator does not record this information.)
L is deallocate () memory, the type is the same as the assignment. (Although Allocator is decoupled with object constructs, memory is still assigned to a particular data type.)
l When writing data in a single memory, we will not be off.
l Never construct two objects at the same location, and will not attempt to destroy the same object twice.
l When deallocate (), make sure that all objects are destroyed first.
As we will see, our Debugging Allocator will not meet all requirements. We can check some of the errors instead of all.
The idea behind Debugging Allocator is very simple [Note 2]: Whenever allocate (), some additional information is recorded in the first few bytes. The user does not see this debug area; we pass the user's pointer to the memory after this. When it is passed to a pointer to the memory block of the memory we allocated, we can reduce its values to view the Debug area, and confirm that the memory block is used correctly.
This design has two hidden issues. First, it is impossible to implement it. We must keep alignment: Suppose the address of the user data needs to be aligned, we have kept some bytes and maintain alignment. How do we know how much? In theory, we can't know; language does not provide mechanisms for judging alignment requirements. (Perhaps this will increase to future standards). In practice, it is not a serious portability: all things on Double Word, there is a good thing on the most platforms, and it is easy to make corresponding modifications on a more stringent platform. The second question is that in this design, some mistakes are easy to check, and others can't. The user gets a memory via allocate () and passes it to deallocate (), so this design is easy to check that allocate () and deallocate () are consistent. Unfortunately, it is difficult to verify that construct () and Destory () are consistent.
The problem is that the parameters typically pass to construct () and Destory () are not the pointer returned from allocate (). If you write down A.Construct (p, x), then P must point to the memory block allocated by A - is pointing to the inside, not pointing (starting). Perhaps the user has assigned a memory of 1000 elements with P1 = A.allocate (1000). In this case, we don't know that the first parameter of construc () is P1, P1 5, or P1 178. We can't find the required debugging information, because it can't find the start address of the assigned memory block.
This issue has two possible solutions, but they are not working very well. First, it is obvious that we can give up all Debugging information must put the idea of the memory block. However, this is not how it can be, because we will have to mix our information with user data. This will destroy the algorithm of the pointer: users cannot step into the next element from one element without knowing our debugging information. Another option is that we can further maintain an additional data structure: For example, we can maintain a std :: set of saving activity object information, users use construct () to create an object, add an address in the SET, user Remove this address every time you use Destory ().
This technology is simple and elegant, and the reason it cannot work is very subtle. The problem is that users don't have to use the same allocator to create and destroy objects: users only need to use an equivalent allocator. Think about the following series of operations:
l Users have given an Allocator, A1, and then make it a copy, A2.
l Use A1.Construct (P, X) created a new object.
l Use A2.DESTROY () destroyed objects.
This sequence is legal, but the allocator of the maintenance activity object list will indicate that it is an error: We add new objects to the A1's active object list, and you will not find it when you use A2 to destroy the object.
Can you bypass this problem by sharing a list of all given allocator? Maybe, but we will fall into the question. in case:
MY_Allocator
MY_Allocator
Then A1 and A2 should share the same activity object list? (The answer seems to be "not", then how to do when_allocator
The main purpose of this Debugging Allocator is to ensure that allocate () and deallocate () are consistently used. When allocated memory, we retain two Word memory at the beginning of each memory, and record the number of elements in the memory block, and a Hash code originating (from the name of the type, especially TypeId) (T) .Name () given). Then we have retained another word in the place where the memory block is completed, and the other copy of the Hash code is stored as a sentinel. Then when the DEALLOCATE () memory block, we check the number of elements that have been stored and the parameters of the incoming parameters are the same, and the two haveh codes are correct. We call Assert () so that an inconsistent behavior will lead to the process failure.
This has not given all the inspections we expect, but it makes us ensure that the memory to deallocate () is this allocator assignment, and is the allocation and return of the same type, and the number is also consistent. It also gives a limited protected: an error in any direction, the error will overwrite the sentinel, and this error will be detected when returned.
A Allocator Adaptor
I didn't show any code until now, because I haven't described any exact form of Debugging Allocator. A simple option is based on Malloc or Std :: Allocator to implement Debugging Allocator. In this way, only one template parameter is required: the type of object to be assigned. This is not as universal as we expect: users cannot use a custom allocator to cooperate with test. For more common, it is best to write Debugging Allocator as an Allocator Adaptor. (So another motivation, I admit that it is for teaching purposes: so we can explore the general characteristics of Allocator Adaptor.)
Write an Allocator Adaptor creates two new issues. The first is that we can't make any assumptions on things being adapted. We can't think of the type of allocator :: Pointer is T *, and you can't think that things can be placed in unin-initialized memory (even the built-in data type, such as CHAR and INT). We must use construct () and destroy () sincerely. Although hate, just add some attention.
The second question is a design problem: What should our debugging allocator look like? The first idea may be that there should be only one template parameter: a template parameter of a template. However, this is not universal: the template parameters of the template are only better for specific numbers, and allocator does not limit this. The template parameters of the template are enough to default allocator (std :: allocator
So how is a normal template parameter? We may want to write:
Template
Class Debug_allocator; fast. Users only need to write debug_allocator
TypedEf debug_allocator
Typedef Typename A :: Template Rebind
The problem is that the value_type of the A2 is Void, and some things inside allocator are not established. For example, there is a Reference's typedef, and Void & It is meaningless; it will cause compilation errors. The default allocator has a specialization, std :: allocator
We can't explicitly indicate that we need a specialized version of Debug_allocator
When we have this method, it is not difficult to set all the things together: complete debug allocator is seen in List 1. You may find that debug_allocator is quite safe when you need to check your container class, but more importantly, you can use it as a prototype. DEBUG_ALLOCATOR is used on your own Allocator Adaptor.
Listing 1: Complete Implementation of The Debugging Allocator
Template
Class Debug_allocator {
Public: // typedefs from Underlying Allocator.
TypedEf TypeName Allocator :: Size_Type Size_Type;
TypeDef TypeName Allocator :: Difference_Type Difference_type;
Typedef Typename Allocator :: Pointer Pointer;
TypeDef Typename Allocator :: Const_Pointer Const_Pointer;
TypedEf TypeName Allocator :: Reference Reference;
TypedEf TypeName Allocator :: const_reference const_reference;
TypedEf TypeName Allocator :: Value_Type Value_type;
Template
Typedef TypeName Allocator :: Template Rebind :: Other A2; Typedef Debug_allocator
}
Public: // Constructor, Destructor, etc.
// Default constructor.
Debug_allocator ()
: alloc (), hash_code (0)
{compute_hash ();
// constructor from an underlying allocator.
Template
Debug_allocator (Const Allocator2 & A)
: Alloc (a), hash_code (0)
{compute_hash ();
// Copy Constructor.
Debug_allocator (const debug_allocator & a)
: Alloc (a.alloc), hash_code (0)
{compute_hash ();
// Generalized Copy Constructor.
Template
Debug_allocator (const debug_allocator
: Alloc (a.alloc), hash_code (0)
{compute_hash ();
// deStructor.
~ debug_allocator () {}
Public: // Member functions.
// the only intending ones
// area allocate and deallocate.
Pointer Allocate (size_type n, const void * = 0);
Void Deallocate (Pointer P, Size_Type N);
Pointer Address (Reference X) const {return a.address (x);
const_pointer address (const_reference x) const {
Return A.Address (x);
}
Void Construct (Pointer P, Const Value_Type & X);
Void Destroy (POINTER P);
SIZE_TYPE MAX_SIZE () const {return a.max_size ();
Friend Bool Operator == (Const Debug_allocator & X,
Const debug_allocator & y)
{RETURN X.Alloc == Y.Alloc;
Friend Bool Operator! = (Const Debug_allocator & x,
Const debug_allocator & y)
{Return x.alloc! = y.alloc;
Private:
Typedef Typename Allocator :: Template Rebind
CHAR_ALLOC;
Typedef Typename Allocator :: Template Rebind
SIZE_ALLOC;
// Calculate the hash code, and store it in this-> hash_code. // Only Used in the constructor.
Void compute_hash ();
Const char * hash_code_as_bytes ()
{RETURN Reinterpret_cast
// Number of Bytes Required to Store N Objects of Type Value_Type.
// DOES NOT INCLUGGING INCLUGGING.
SIZE_TYPE DATA_SIZE (SIZE_TYPE N)
{RETURN N * SIZEOF (Value_Type);
// Number of Bytes Allocated in Front of the User-Visible Memory
// block. Must Be Large Enough To Store Two Objects of Type
// size_t, and to preserve alignment.
SIZE_TYPE PADDING_BEFORE (SIZE_TYPE)
{RETURN 2 * SIZEOF (std :: size_t);}
// Number of Bytes from the beginning of the block we allocate
// Until the beginning of the seninel.
SIZE_TYPE SENTINEL_OFFSET (SIZE_TYPE N)
{RETURN DATA_SIZE (N) Padding_Before (N);
// Number of bytes in the Sentinel.
Size_type Sentinel_size ()
{RETURN SIZEOF (std :: size_t);}
// size of the area we allocate to store n objects,
// inclished overhead.
SIZE_TYPE TOTAL_BYTES (SIZE_TYPE N)
{RETURN DATA_SIZE (N) Padding_Before (N) Sentinel_Size ();
Allocator alloc;
Std :: size_t hash_code;
}
// Specialization When the value type is void. We provide Typedefs
// (And NOT Even All of Those), And We Save The Underlying Allocator
// So We can Convert Back to some Other Type.
Template
Class Debug_allocator
PUBLIC:
TypedEf TypeName Allocator :: Size_Type Size_Type;
TypeDef TypeName Allocator :: Difference_Type Difference_type;
Typedef Typename Allocator :: Pointer Pointer;
TypeDef Typename Allocator :: Const_Pointer Const_Pointer;
TypedEf TypeName Allocator :: Value_Type Value_type;
Template
Typedef debug_allocator
}
Debug_allocator (): alloc () {}
Template
Debug_allocator (Const A2 & a): Alloc (a) {}
Debug_allocator (const debug_allocator & a): alloc (a.alloc) {}
Template
Debug_allocator (const debug_allocator
ALLOC (a.alloc) {}
~ debug_allocator () {}
Private:
Allocator alloc;
}
// Noninline Member Functions for debug_allocator. They area not defined
// for the void specialization.
Template
TypeName Debug_allocator
Debug_allocator
(SIZE_TYPE N, Const void * = 0) {
askERT (n! = 0);
// Allocate Enough Space for n Objects of Type T, Plus the Debug
// Info at the beginning, plus a one-byte Sentinel at the end.
TypeDef Typename Char_alloc :: Pointer Char_pointer;
TypedEf TypeName Size_alloc :: Pointer Size_Pointer;
CHAR_POINTER Result = CHAR_ALLOC (alloc) .allocate (Total_Bytes (n));
// Store the size.
SIZE_POINTER Debug_area = size_point (result);
SIZE_ALLOC (Alloc) .construct (Debug_area 0, N);
// Store a hash code based on the type name.
Size_alloc (alloc) .construct (debug_area 1, hash_code);
// Store The Sentinel, Which is Just The Hash Code Again.
// for Reasons Of Alignment, We Have To Copy It by by byte.
Typename Char_alloc :: Pointer Sentinel_Area =
Result Sentinel_offset (N);
Const char * SENTINEL = hash_code_as_bytes ();
{
Char_alloc ca (alloc);
INT i = 0;
Try {
For (; i Ca.construct (Sentinel_Area i, Sentinel [i]); Catch (...) { For (int J = 0; j Ca.Destroy (& * (Sentinel_Area J)); Throw; } } // Return a Pointer to the user-visible portion of the memory. Pointer Data_Area = POINTER (Result Padding_before (n)); Return Data_Area; } Template Void Debug_allocator (Pointer P, size_type n) { askERT (n! = 0); // Get a pointer to the space where we put the debugging information. TypeDef Typename Char_alloc :: Pointer Char_pointer; TypedEf TypeName Size_alloc :: Pointer Size_Pointer; Char_pointer cp = char_pointer (p); SIZE_POINTER Debug_area = size_pointer (cp - padding_before (n)); // Get the size request and the hash code, and check for consistency. SIZE_T Stored_n = Debug_Area [0]; SIZE_T Stored_hash = Debug_Area [1]; askERT (n == stored_n); Assert (haveh_code == stored_hash); // Get The Sentinel, And Check for Consistency. Char_pointer Sentinel_Area = Char_pointer (debug_area) Sentinel_offset (N); Const char * SENTINEL = hash_code_as_bytes (); Assert (std :: equal (Sentinel, Sentinel Sentinel_size (), Sentinel_Area); // deStroy Our debugging information. Size_alloc (alloc) .destroy (Debug_area 0); Size_alloc (alloc) .destroy (Debug_area 1); For (size_type i = 0; i Char_alloc (alloc) .destroy (Sentinel_Area i); // Release The Storage. Char_alloc (alloc) .deallocate (cp - padding_before (n), total_bytes (n)); } Template Void Debug_allocator Value_type & x) { ASSERT (P); A.Construct (p, x); Template Void Debug_allocator { ASSERT (P); A.DESTROY (P); } Template Void Debug_allocator Const char * name = typeid (value_type) .name (); Hash_code = 0; For (; * name! = '/ 0'; Name) Hash_code = hash_code * (size_t) 37 (size_t) * name; Note: [1] Matt Austern. "The Standard Librarian: What Are Allocators Good for?" C / C Users Journal C Experts Forum, December 2000, [2] this debugging allocator is based on the one in the sgi library,
