分享
 
 
 

CUJ:标准库:调试用的Allocator

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

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.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有