STL 剖析:空间配置器(allocator)

 
 
C++
 3.6k
 

在实现 TinySTL 过程中对思路的一些梳理,并不涉及代码(大概),如有兴趣可以跳至相关实现。本篇主要讲述 STL 中的空间配置器,其对于实现 STL 有着举足轻重的地位,虽然它总是掩藏在一切组件的背后,默默工作,但是 STL 操作实际均发生在容器之中,而容器是一定需要配置空间来放置的,所以这地位你懂得😉

2024-08-02 22:47:19

目录:

SGI 标准的空间配置器,std::allocator

构造和析构基本工具:construct()destroy()

空间的配置与释放,std::alloc


SGI 标准的空间配置器,std::allocator

allocator 在 SGI 中从未使用过,也不建议我们使用。原因是 allocator 仅仅是对 C++ 的内存配置基本操作::operator new::operator delete的一层薄薄的包装,并没有任何效率上的优化考虑。但是对于我们来说,还是值得实现一下的,一来是可以用来练手,熟悉熟悉 STL 规范的空间配置器的标准接口;二来只有经历了这样的做法后,在之后体验 SGI STL 对于空间配置器的美妙设计才能刻苦铭心😊

其中值得一提的是,一般而言,我们所熟知的 C++ 的内存配置和释放操作是:

1
2
3
class Entity {...};
Entity *entity = new Entity; // 这里的 new 包含内存配置和构造对象两个操作
delete *entity; // 同理,delete 也包含析构对象和释放内存两个操作

new操作符包含两阶段操作:(1)调用::operator new配置内存;(2)调用Entity::Entity()构造对象,delete操作符包含两阶段操作:(1)调用Entity::~Entity()析构对象;(2)调用::operator delete释放内存

在 STL allocator 中将这两阶段操作分开了,以便更加精细的操作。其中alloc::allocate()alloc::deallocate()负责内存的配置和释放,而::construct()::destroy()负责构造和析构对象,并且于 stl_construct.h 定义全局函数construct()destroy()。至此大致目录结构为:

构造和析构基本工具:construct()destroy()

construct()函数的用途就是将初值设定到指针所指的空间上,这里的初值就是构建的对象,而所谓指针所指的空间则是配置器 allocator 中配置的内存空间。针对这一任务,C++ 的 placement new 可以很好的解决::new(static_cast<void *>(ptr)) T();

destroy()有两个版本,第一个版本接受一个指针,直接调用该对象的析构函数即可;第二个版本接受firstlast两个迭代器,由于是一个范围,这里会产生一个问题:我们不知道这范围究竟有多大,如果范围很大,一次次地调用即便每个对象的析构函数都无关痛痒(即 trivial destructor)对于效率都是一种伤害。因此这里会进行一些处理,首先对利用value_type()获得迭代器所指对象的型别(亦称类型),再利用__type_traits<T>判断该型别的析构函数是否无关痛痒,如果是(std::true_type),则什么都不做;如果不是(std::false_type),则循环整个范围,并在循环中每经历一个对象则调用版本一的destroy()

空间的配置与释放,std::alloc

对于 <std_alloc.h>,SGI 有如下设计哲学:

  • 向 system heap 索要空间
  • 考虑多线程(multi-threads)状态
  • 考虑内存不足时的应变措施
  • 考虑过多“小型区块”可能造成的内存碎片(fragment)问题

这里由于个人的能力有限,关于多线程状态的讨论暂时排除

在《STL 源码剖析》中侯捷先生提到双层级配置器的设计处理了 fragment 问题,在这里提出一些个人的拙见以作补充,双层级配置器的设计,特别是第二级配置器对于整个设计哲学做了很多处理,在 memory pool 的设计中得以具体的体现,有关 memory pool 下文会有所论述

SGI 双层级配置器,第一级配置器以 malloc()free()realloc()等 C 函数执行实际的内存配置、释放、重配置操作,并实现类似 C++ new-handler 的机制。是的,不能直接使用 C++ new-handler 机制,因为 SGI 以malloc()而非::operator new来配置内存,也因此,SGI 不能直接使用 C++ 的set_new_handler(),必须仿真一个类似的set_malloc_handler()。这其中的原因,侯捷先生提出两个推测,一是历史因素,二来是 C++ 并未提供相应于realloc()的内存配置

所谓 C++ new-handler 机制是,你可以要求系统在内存配置需求无法被满足时,调用一个你所指定的函数。换句话说,一旦::operator new无法完成任务,在抛出std::bad_alloc异常状态之前,会先调用由客端指定的处理例程。该处理例程通常即被称为 new-handler。

请注意,SGI 第一级配置器的allocate()reallocate()都是在调用malloc()realloc()不成功后,改调用oom_malloc()oom_realloc()(oom 即 out of memory)。后两者都有内循环,不断调用set_malloc_handler(),期望在某次调用之后,获得足够的内存而圆满完成任务。如果客端并没有设置set_malloc_handler(),后两者则毫不客气地调用__THROW_BAD_ALLOC,抛出 bad_alloc 信息,或利用exit(1)硬生生终止程序

请记住,设计和设定 out-of-memory 机制是客端的责任,并且 out-of-memory 机制(处理例程)解决问题的做法有特定的模式,具体请参考《Effective C++》2e 条款 7

SGI 第二级配置器则视情况的不同采用不同的策略,如果区块够大,超过 128 bytes 时,就移交第一级配置器处理。当区块小于 128 bytes 时,则以 memory pool 管理,并且在极特殊的情况下 memory pool 会调用第一级配置器的 out-of-memory 机制,这一点会在之后 memory pool 的剖析中提及。通过 memory pool 管理又被称为次层配置:每次配置一大块内存,并维护对应的自由链表(free-list)。下次若再有相同大小的内存需求,就直接从 free-lists 中拨出。如果客端释还小额区块,就由配置器回收到 free-lists 中。为了管理方便 SGI 第二级配置器会主动把任何小额区块的内存需求量上调至 8 的倍数

这里有关 free-lists 的结构设计很有意思,通过union实现了类型双关这一编程技巧:

1
2
3
4
union obj {
union obj *next;
char client_data[1];
};

在使用类型双关后,节点既可视为一个指针指向下一个节点用以链接下一个节点,又可视为一个指针指向实际区块用以存储数据,一物二用,节点不再需要存储一个额外的指针(指向下一个节点)。由于union特性,同一时间只能存储其中一个成员的数据,因此我们得以一窥区块释放的本质,其就是区块在重新加入 free-lists 时存储在区块中的实际数据被节点地址覆盖了

从 memory pool 取空间可以说是第二级配置器的精髓所在,将 memory pool 的内存空间比作水量。如果水量充足,直接划拨 20 个区块给 free list。如果水量不足划拨 20 个区块,但足以划拨一个及以上的区块,就尽可能的将这部分空间划拨出去。但如果连一个区块都无法提供,这对客端显然无法交代,此时便利用malloc()从 heap 配置内存,为 memory pool 注入源头活水以应付需求。新水量的大小为需求量的 2 倍,再加上一个随着配置次数增加而越来越大的附加量(也就是 历史需求量 / 16)。其中一半区块留存在 memory pool 中,另一半区块除去抽取一个交给客端,剩余的交给 free list 维护

如果 system heap 空间山穷水尽(以至无法为 memory pool 注入源头活水),malloc()失败,memory pool 就四处寻找 free list 中“尚有未用且够大的区块”。找到了交付一块给客端,其余的存入 memory pool 中。找不到就调用第一级配置器寻求 out of memory 处理机制的帮助,试试看能不能释放其它的内存拿来此处使用,如果失败,就抛出 bad_alloc 异常

Comments