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()有两个版本，第一个版本接受一个指针，直接调用该对象的析构函数即可；第二个版本接受first和last两个迭代器，由于是一个范围，这里会产生一个问题：我们不知道这范围究竟有多大，如果范围很大，一次次地调用即便每个对象的析构函数都无关痛痒（即 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