The Standard Librarian ：A Debugging Allocator
Matt Austern
http://www.cuj.com/experts/1912/austern.htm?topic=experts
--------------------------------------------------------------------------------
C++标准库中的Allocator有一个复杂而低层次的接口[注1]。和new与delete不同，它们将内存分配与对象构造解耦。和malloc与free不同，它们要求你明确正在分配的内存的数据类型和对象数目。
通常，这不成为问题。Allocator拥有低层次的接口是因为它们是低层次的概念：它们通常隐藏在容器类内部，而不属于普通用户的代码。然而，有时你可能不得不关心allocator：当你自己写一个新的容器类的时候。Allocator比new/delete难用多了，因此，更容易发生错误。如果你写的代码不得不使用allocator，如何确保代码正确？运行期的测试不能证明不存在错误，只能证明错误的存在。尽管如此，测试还是很重要－－你越快发现bug，它就越早被修正。
所有的标准容器类都接受一个allocator类作为其模板参数；这个参数有一个默认值，比如std::vector<int>是vector<int,std:: allocator<int> >的简写。如果我们写了一个有额外正确性检查的alocator类，那就可以用它代替std::allocator<int>来作为vector的第二模板参数。如果没有bug的话，vector的行为将会和以前一样。(当然，除了额外的检查将使它变慢。)
这篇文章将展示这样一个debugging allocator类。它在其适用范围内是有价值的，并且实现它也是使用allocator的一个有趣练习。
测试
我们想检查什么种类的错误？最重要的是：
l 传给的deallocate()的内存确实是这个allocator分配的。
l 当deallocate()一块内存时，归还了与分配时相同的字节数。（和malloc与free不同，allocator不为自己记录这些信息。）
l 正deallocate()的内存，其类型与分配时相同。(虽然 allocator将内存分配与对象构造解耦了，但内存仍然是为某个特定数据类型分配的。)
l 当在一块内存中写入数据时，我们不会越界。
l 从不试图在同一位置构造两个对象，并且也不会试图销毁同一对象两次。
l 当deallocate()一块内存时，确保先销毁了其中的所有对象。
如我们将要看到的，我们的debugging allocator不会满足所有要求。我们能检查其中的一部分错误，而不是全部。
在debugging allocator背后的主意很简单[注2]：每当allocate()一块内存时，多分配一些，并在最初几个字节中记录一些额外信息。用户看不到这块debug区域；我们传给用户的指针指向在此之后的内存。当传回给我们一个指向我们分配的内存块的指针时，我们可以减小其值以查看debug区域，并确认内存块是被正确使用的。
这样的设计有两个隐藏问题。首先，不可能相当可移植地实现它。我们必须保持对齐：假设用户数据的地址需要对齐，我们保留了一些字节而还要维持对齐。我们如何知道该加多少？理论上，我们无法知道；语言没有提供判断对齐要求的机制。(也许这将会增加到未来的标准中)。实践中，它不是一个严重的可移植性议题：在double word上对齐所有东西，在目前绝大部分平台上都足够好了，并且在要求更严格的平台上作相应修改也很容易。
第二问题是，在这个设计里，有一部分错误很容易检查，而其它的就不行了。用户通过allocate()获得一块内存，并把它传给deallocate()，于是，这个设计很容易检查allocate()和deallocate()是被一致使用的。不幸的是，很难检验construct()和destory()是被一致使用的。
问题是通常传给construct()和destory()的参数不是从allocate()返回的指针。如果写下a.construct(p,x)，那么p必须指向通过a分配出的内存块内部－－是指向内部，而不是指向（其开头）。也许用户通过p1 = a.allocate(1000)分配了足够1000个元素的内存。这种情况下，我们不知道construc()的第一个参数是p1，p1 + 5，还是p1 + 178。我们无法找到需要的debugging信息，因为没法找到分配出的内存块的开始地址。
这个问题有两个可能的解决方案，但都不是工作得很好。首先，明显，我们可以放弃所有的debugging信息都一定要放在内存块开始处的主意。但是，这不怎么能行，因为我们将不得不将我们的信息与用户数据混合存储。这会破坏指针的运算法则：用户无法在不知道我们的debugging信息的情况下从一个元素步进到下一个元素。另外一个选择是，我们可以另外维护一个额外的数据结构：比如，我们可以维护一个保存活动对象信息的std::set，用户每用construct()创建一个对象，就在set中增加一个地址，用户每用destory()销毁一个对象就移除这个地址。
这个技术简单而优雅，而它不能工作的理由很微妙。问题是用户不是必须使用相同的allocator来创建和销毁对象：用户只需要使用一个等价的allocator。思考一下下面的一系列操作：
l 用户被给予了一个allocator, a1，然后作了它的一个拷贝，a2 。
l 用户用a1.construct(p,x)创建了一个新对象。
l 用户用a2.destroy()销毁对象。
这个序列是合法的，但是维护活动对象列表的allocator会指出它是一个错误：我们将新的对象加入到a1的活动对象列表中，而当用a2销毁对象时将找不到它。
可以通过在所有给定的allocator的拷贝间共享列表来绕过这个问题吗？也许吧，但是我们将会陷入定义上的问题。如果：
my_allocator<int> a1;
my_allocator<double> a2(a1);
然后a1和a2应该共享相同的活动对象列表吗？(答案看起来可能是“不”，那么再my_allocator<int>(a2)时怎么办？) 我们也陷入实现上问题：在幕后被共享的对象需特别处理，尤其是在有并发问题时。
因为这些问题，我已经简单地放弃了在construct()和destory()上作实质性检查的主意。这个版本的debugging allocator只在它们的参数上作最小程度的检查，并不试图确保destory()的参数被构造过，或这个对象只销毁一次。
这个debugging allocator的主要目的是确保allocate()和deallocate()被一致使用。当分配内存时，我们在每块内存开始处保留了两个word的内存，并在其中记录了内存块中元素的数目，和一个起源于类型的hash码(从类型的名字，特别是如typeid(T).name()所给出的)。然后我们在内存块结束的地方还保留了另外一个word，并存入了hash码的另一个拷贝作为哨兵。然后当deallocate()内存块时，我们检查已经储存的元素数目与传入的参数相同，已及两个hash码都是正确的。我们调用assert()以便一个不一致的行为将导致程序失败。
这没有给予我们所期望的所有检查，但它让我们确保传给deallocate()的内存是这个allocator分配的，并且是对相同的类型进行的分配和归还，数目也是一致的。它也对越界给予了有限的保护：在任一方向的越界一个的错误都会覆盖哨兵，而这个错误将会在归还时被检测到。
一个Allocator Adaptor
到现在为止我都没有展示任何代码，因为我还没有描述debugging allocator的任何精确形式。一个简单的选择是基于malloc或std::allocator来实现debugging allocator。这样的话，只需要一个模板参数：将要分配的对象的类型。这不如我们所期望得那么通用：用户无法使用一个自定义的allocator来配合测试。为了更通用，最好将debugging allocator写成一个allocator adaptor。(这样做的另外一个动机，我承认，是为了教学目的：于是我们可以探索allocator adaptor的通用特征。)
写一个allocator adaptor产生了两个新的问题。第一是我们不能对正在适配的东西作任何假设。我们不能想当然地认为Allocator::pointer的类型是T *，也不能认为可以将东西放入未初始化的内存中（即使是内建数据类型的东西，如char和int）。我们必须虔诚地使用construct()和destroy()。虽然讨厌，但只要加些注意就行了。
第二个问题是一个设计问题：我们的debugging allocator的模板参数看起来应该是什么样子？第一个想法可能是应该仅有一个模板参数：一个模板的模板参数。然而，这不足够通用：模板的模板参数只对特定数目的实参来说才比较好，而allocator没有这样的限定。模板的模板参数对默认allocator（std::allocator<T>）是够了，但对有额外参数的用户自定义allocator就不行了，如my_allocator<T,flags>。
那么一个普通的模板参数怎么样？我们可能想写：
template <class Allocator>
class debug_allocator;
快了。用户只需写debug_allocator<std:: allocator<int> >。不幸的是，还有一个问题。allocator的value_type可能是void，某些情况下这很有用、很重要(我在以前的文章中描述过)。如果用户这么写了，会发生什么？
typedef debug_allocator<std::allocator<int> > A;
typedef typename A::template rebind<void>::other A2;
问题是A2的value_type是void，而allocator内部的一些东西对void是不成立的。例如，有一个reference的typedef，而void &是没有意义的；它会导致编译错误。默认的allocator有一个特化，std::allocator<void>。没有理由地，我们也需要一个特化。
我们没法明确地表示出在Allocator的value_type是void时，我们需要debug_allocator<Allocator>的一个特化版本。但有一个次好的方法。我们可以给debug_allocator第二个模板参数，它默认是Allocator::value_type，于是可以在第二模板参数是void时写一个特化了。第二个模板参数完全是实现细节：用户不需要显式写出来，通过写下（例如）debug_allocator<std:: allocator<int> >能推导出来。
当我们有了这个方法后，将所有的东西集在一起就不难了：完整的 debug allocator见于List 1。 你可能会发现debug_allocator在需要检查你的容器类对内存的使用时颇有用处，但更重要的是你能把它作为原型。debug_allocator上使用的实现技巧对你自己的allocator adaptor很有用处。
Listing 1: Complete implementation of the debugging allocator
template <class Allocator, class T = typename Allocator::value_type>
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 <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_allocator<A2, typename A2::value_type> other;
};
public: // Constructor, destructor, etc.
// Default constructor.
debug_allocator()
: alloc(), hash_code(0)
{ compute_hash(); }
// Constructor from an underlying allocator.
template <class Allocator2>
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 <class A2, class T2>
debug_allocator(const debug_allocator<A2, T2>& a)
: alloc(a.alloc), hash_code(0)
{ compute_hash(); }
// Destructor.
~debug_allocator() {}
public: // Member functions.
// The only interesting ones
// are 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>::other
char_alloc;
typedef typename Allocator::template rebind<std::size_t>::other
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<const char*>(&hash_code); }
// Number of bytes required to store n objects of type value_type.
// Does not include the overhead for debugging.
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 sentinel.
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,
// including 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 Allocator>
class debug_allocator<Allocator, void> {
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 <class U> struct rebind {
typedef typename Allocator::template rebind<U>::other A2;
typedef debug_allocator<A2, typename A2::value_type> other;
};
debug_allocator() : alloc() { }
template <class A2>
debug_allocator(const A2& a) : alloc(a) { }
debug_allocator(const debug_allocator& a) : alloc(a.alloc) { }
template <class A2, class T2>
debug_allocator(const debug_allocator<A2, T2>& a) :
alloc(a.alloc) { }
~debug_allocator() {}
private:
Allocator alloc;
};
// Noninline member functions for debug_allocator. They are not defined
// for the void specialization.
template <class Allocator, class T>
typename debug_allocator<Allocator, T>::pointer
debug_allocator<Allocator, T>::allocate
(size_type n, const void* = 0) {
assert(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_pointer(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 byte 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 < sentinel_size(); ++i)
ca.construct(sentinel_area + i, sentinel[i]);
}
catch(...) {
for (int j = 0; j < i; ++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 <class Allocator, class T>
void debug_allocator<Allocator, T>::deallocate
(pointer p, size_type n) {
assert(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];
assert(n == stored_n);
assert(hash_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 < sentinel_size(); ++i)
char_alloc(alloc).destroy(sentinel_area + i);
// Release the storage.
char_alloc(alloc).deallocate(cp - padding_before(n), total_bytes(n));
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::construct(pointer p, const
value_type& x)
{
assert(p);
a.construct(p, x);
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::destroy(pointer p)
{
assert(p);
a.destroy(p);
}
template <class Allocator, class T>
void debug_allocator<Allocator, T>::compute_hash() {
const char* name = typeid(value_type).name();
hash_code = 0;
for ( ; *name != '\0'; ++name)
hash_code = hash_code * (size_t) 37 + (size_t) *name;
注：
[1] Matt Austern. "The Standard Librarian: What Are Allocators Good For?" C/C++ Users Journal C++ Experts Forum, December 2000, <www.cuj.com/experts/1812/austern.htm>.
[2] This debugging allocator is based on the one in the SGI library, <www.sgi.com/tech/stl>. The original version was written by Hans-J. Boehm.
