第二章 空间配置器(allocator)
1. 空间配置器的标准接口
1.1 一般接口(generalized)
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
1.2 特殊化接口(specified)
接口 | 作用 |
---|---|
allocator::rebind | 旨在帮助allocator为不同类型的元素分配空间,即使allocator已被指定为一个对象分配空间。 |
allocator::allocator() | 默认构造函数 |
allocator::allocator(const allocator&) | 拷贝函数 |
template<class U>allocator::allocator(const allocator<U>&) | 泛型拷贝函数 |
allocator::~allocator() | 默认析构函数 |
pointer allocator::address(reference x) const | 返回指定对象的地址,例如:a.address(x) <=> &x |
pointer allocator::allocate(size_type n, const void* = 0) | 配置空间,用来存储n个类型为T的对象,第二个参数主要用于优化内存优化和管理 |
allocator::deallocate(pointer p, size_type n) | 释放之前所分配的内存 |
allocator::allocator::max_size() const | 返回所成功分配的最大内存大小的值 |
allocator::destroy(pointer p) | 等价于 p->T() |
用一个例子对allocator::rebind
进行补充:
template<class T>
class alloc;
template<typename T, typename Alloc = alloc<T>>
class MyContainer{
public:
template<typename U>
struct rebind{
typedef Alloc<U> other; // Allocator type for type U
// other represents some other objects
};
};
C++1.3 设计一个简单的空间配置器
#include <new> // for placement new
#include <cstddef> // for ptrdiff_t, size_t
#include <cstdlib> // for exit()
#include <climits> // for UINT_MAX
#include <iostream> // for cerr
#include <vector> // for test
namespace T_ {
// allocate memory
template<class T>
inline T* _allocate(ptrdiff_t size, T*) {
std::set_new_handler(0); // invoke when out of memory
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)))); // allocate memory
if (tmp == 0) { // the allocated memory is 0, which means that allocating memory fails
std::cerr << "out of memory" << '\n';
exit(0); // terminate processs
}
return tmp; // return the pointer of the allocated memory block
}
// release memory
template<class T>
inline void _deallocate(T* buffer) {
::operator delete(buffer); // release the allocated memory
}
// constructor
template<class T1, class T2>
inline void _construct(T1* p, const T2& value) {
new(p) T1(value); // assign value at pointer p
}
// destructor
template<class T>
inline void _destroy(T* ptr) {
ptr->~T(); // invoke the destructor of type class
}
template<class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
/*-----implement part of the specific API-----*/
// allocator::rebind->rebind allocator of type U
template<class U>
struct rebind {
typedef allocator<U> other;
};
// pointer allocator::allocate->hint used for locality
pointer allocate(size_type n, const void* hint = 0) {
return _allocate((difference_type)n, (pointer)0);
}
// allocator::deallocate
void deallocate(pointer p, size_type n) { _deallocate(p); }
// allocator::construct
void construct(pointer p, const T& value) {
_construct(p, value);
}
// allocator::destroy
void destroy(pointer p) { _destroy(p); }
// pointer allocator::address
pointer address(reference x) { return (pointer)&x; }
// const_pointer allocator::const_address
const_pointer const_address(const_reference x) {
return (const_pointer)&x;
}
// size_type allocator::max_size()
size_type max_size() const {
return size_type(UINT_MAX / sizeof(T));
}
};
}
int main() {
int ia[5] = { 0, 1, 2, 3, 4 };
unsigned int i;
std::vector<int, T_::allocator<int>> iv(ia, ia + 5);
for (i = 0; i < iv.size(); i++) std::cout << iv[i] << ' ';
std::cout << '\n';
return 0;
}
C++此处的STL设计只是一个简易的allocator。
2. SGI空间配置器
SGI配置器与一般的allocator有所不同
名称 | 语法 | 是否接受参数 | 编译器 | |
---|---|---|---|---|
GENERAL | allocator | vector<int, std::allocator<int>> iv | 是 | VC or VB |
SGI | alloc | vector<int, sd::alloc> iv | 否 | GCC OR G++ |
尽管SGI的alloc与标准的allocator有所不同,但是这并不影响使用,因为一般都是用缺省的方式对alloc进行声明。
SGI的每一个容器都使用缺省的空间配置器alloc,如下所示
template<class T, class Alloc = alloc> // 缺省使用alloc为配置器
class vector{ ... };
C++2.1 SGI标准的空间配置器 std::allocator
在SGI内部也有一个名为allocator
的配置器,但是相比较于标准的空间配置器,它的效率较低,两者差 异在于前者把C++
的 ::operator new
和 ::operator delete
进行了简单的包装。
以下是SGI_style的allocator
实现。
注:SGI_style的allocator
只接受void*
类型的参数。
#include <new>
#include <cstddef>
#include <cstdlib>
#include <limits>
#include <iostream>
#include <algorithm>
#include <vector>
/*-----generalized_style-----*/
template<class T>
inline T* allocate(ptrdiff_t size, T*)
{
std::set_new_handler(0);
T* tmp = (T*)(::operator new ((size_t)(size * sizeof(T))));
if(tmp == 0)
{
std::cerr << "out of memory" << '\n';
exit(1);
}
return tmp;
}
template<class T>
inline void deallocate(T* buffer)
{
::operator delete(buffer);
}
/*-----SGI_style-----*/
template<class T>
class allocator
{
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T* const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
pointer allocate(size_type n)
{
return ::allocate((difference_type)n, (pointer)0);
}
/*-----in the book-----*/
/*void deallocate(pointer p) { ::deallocate(p); }
this deallocate is not runnable */
/*-----and the below "deallocate" is runnable --------------*/
void deallocate(pointer p, size_type n) { ::deallocate(p); }
pointer address(reference x) { return (pointer)&x; }
const_pointer const_address(const_reference x)
{
return (const_pointer)&x;
}
size_type init_page_size()
{
return std::max(size_type(1), size_type(4096 / sizeof(T)));
}
size_type max_size() const
{
return std::max(size_type(1), size_type(UINT_MAX / sizeof(T)));
}
};
int main() {
int ia[5] = { 0, 1, 2, 3, 4 };
unsigned int i;
std::vector<int, allocator<int>> iv(ia, ia + 5);
for (i = 0; i < iv.size(); i++) std::cout << iv[i] << ' ';
std::cout << '\n';
return 0;
}
C++2.2 SGI特殊的空间配置器 std::alloc
SGI_style的std::alloc
相比较于SGI_style的std::allocator
而 言,前者对基层内存配置/释放(operator::new
& operator::delete
)进行了效率优化。
一般在C++中关于对象对内存的配置和释放的操作
class Foo { ... };
Foo* pf = new Foo; // allocate memory, then construct object
delete pf; // destruct object, and release memory
关于内存配置和释放的流程如下
第一阶段 | 第二阶段 | |
---|---|---|
new | 调用::operator new 配置内存 | 调用Foo::Foo() 构造对象 |
delete | 调用Foo::~Foo() 析构对象 | 调用::operator delete 释放内存 |
简单来讲就是:
- 造一个房子
::operator new
- 人住进去
Foo::Foo()
- 人走了
Foo::~Foo()
- 再把房子给拆了
::operator delete
在STL allocator中对上面的步骤有精细的分工:
alloc::allocate()
配置空间alloc::deallocate()
释放空间alloc::construct()
构造对象alloc::destroy()
析构对象
在STL标准中,allocator定义与<memory>
中,SGI<memory>
中包含如下两个文件
#include<stl_alloc.h> // for allocating and deallocating of memory
#include<stl_construct.h> // for constructing and destructing of object
C++2.3 构造和析构基本工具: construct()
& destroy()
对上图内容的代码化:
prefix specified
#include <new> // for placement new
template<class T1, class T2>
inline void construct(T1* p, const T2& value){
new(p) T1(value); // placement new -> invoke T1::T1(value);
}
C++第一版destroy()
specified
template<class T>
inline void destroy(T* pointer){
pointer->~T(); // invoke ~T()
}
C++pointer->~T();
一般析构。
第二版destroy()
generalized
template<class T>
inline void destroy(ForwardIterator first, ForwardIterator last){
__destroy(first, last, value_type(first));
}
C++__destroy(first, last, value_type(first));
根据元素的类型选择最合适的方式进行析构。
第二版destroy()
SE
- SE1(char* ver.) ->
inline void destroy(char*, char*) {}
- SE2(wchar_t* ver.) ->
inline void destroy(wchar_t*, wchar_t*) {}
判断元素类型是否有trivial destructor
generalized
template<class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*){
typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
__destroy_aux(first, last, trivial_destructor());
}
C++- 元素类型有
non-trivial destructor
specified
templace<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type){
for(; first < last; ++first) destroy(&*first);
}
C++- 元素类型有
trivial destructor
specified
template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type){}
C++补充和解释:
- 用来构造、析构的函数都为全局函数(STL规范:配置器必须拥有名为construct() 和 destroy() 两个成员函数)
- 上面的
construct()
接受一个 指针p 和一个 初值value-> 将初值设定到指针所指的位置 =>placement new()
- 第一版
destroy()
接受一个指针,用于析构掉指针所指的对象。第二版destroy()
接受first
和last
两个迭代器,用于析构掉*[first, last)*范围内的所有对象 - 在对象析构之前需要考虑该对象所有的析构函数是否trivial->
value_type()
(获取对象类型) ->__type_traits<T>
(判断该类型对象的析构函数是否trivial)
4.1 是(__true_type)
,直接忽略
4.2 否(__false_type)
,对范围内的对象逐个进行destroy() (第一版)
2.4 空间的配置与释放 std::alloc
一般地,在对象构造前,要对其进行空间的配置,在对象析构后,要对配置的内存进行释放。 在SGI中,上述过程实现流程如下:
- 向 system heap 申请空间
- 考虑多线程(multi-threads )状态
- 考虑内存不足时的应变措施
- 考虑内存分配时可能导致的内存碎片问题
内存碎片:不同的对象构造需要申请不同的大小的内存空间,但可能由于分配得不够合理(有大有小),导致会有一些较小的内存区块(这部分内存区块无法满足目标对象构造的内存需求)残留,随着时间的推移这些小的内存区块会越来越多,即使总的剩余内存足够大,但是已无法为大型的对象分配空间,因此造成内存浪费。
内存碎片可能会导致的问题:
- 碎片化的可用空间
- 内存使用效率低下
- 分配失败的概率增加
- 性能下降
内存碎片问题的可能解决方法:
- 使用固定大小的内存池:预分配固定大小的内存区块
- 自定义内存配置器:根据实际需求进行内存分配
- 内存压缩:手动对内存碎片进行清理
- 智能内存管理:RAII和智能指针
- 限制动态内存分配:对小型、生命周期短的对象使用基于堆栈的内存分配,对大型、生命周期长的对象使用动态内存分配
在C++中,对内存进行配置的操作是::operator new()
,对内存进行释放的操作是::operator delete()
。
可类比C中的malloc()
和free()
函数。
同时,在SGI中也是通过malloc()
和free()
两个函数来实现对内存的配置和释放。
考虑到上面提到的内存碎片问题,SGI设计了双层级的内存配置器:
#ifdef
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc; // set alloc as primary allocator
#else
// set alloc as secondary allocator
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif
C++- 第一级配置器直接使用
malloc()
和free()
- 第二级配置器则根据情况采用不同的分配策略:
- 当需要配置的内存区块大于128bytes时,使用一级配置器
- 当需要配置的内存区块小于128bytes时,使用二级配置器 -> memory pool (内存池)
SGI会为双层及的配置器封装一个如下的接口(为了使接口符合STL的标准):
template<class T, class Alloc>
class simple_alloc{
public:
static T* allocate(size_t n){
return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));
}
static T* allocate(void){
return (T*) Alloc::allocate(sizeof(T));
}
static void deallocate(T* p, size_t n){
if(0 != n) Alloc::deallocate(p, n * sizeof(T));
}
static void deallocate(T* p){
Alloc::deallocate(p, sizeof(T));
}
};
C++综上可见,该接口内的成员函数都是调用配置器内的成员函数,其中的配置单位为目标元素的大小sizeof(T)
。
SGI的STL容器全都使用simple_alloc
这个接口,如:
template<class T, class Alloc = alloc> // default
class vector{
protected:
// specified allocator that allocates a size of element per time
typedef simple_alloc<value_type, Alloc> data_allocator;
void deallocate(){
if(...) data_allocator(start, end_of_storage - start);
}
...
};
C++第一级配置器与第二级配置器关系图
第一级配置器与第二级配置器的包装接口和运用方式关系图
2.5 第一级配置器 __ malloc_alloc_template 剖析
#if 0
# include <new>
# define THROW_BAD_ALLOC throw bad_alloc
#elif #defined(__THROW_BAD_ALLOC)
# include <iostream>
# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1);
#endif
C++特点:
- malloc-base allocator 比 default allocator速度慢
- 一般而言是thread-safe,内存空间利用率较高
注:
- 无参模板用法
template<>
中定义内置类型与变量名,在实例化时直接给该变量赋值。
template<int inst>
class ex{
public:
void printf() { std::cout << "inst: " << inst; }
};
int main(){
/* ex<para> e1; here para = inst */
ex<3> e1;
e1.printf();
return 0;
}
C++static
修饰符用法
static | non-static | |
---|---|---|
with instance | accessible | accessible |
without instance | accessible | inaccessible |
*this | inaccessible | accessible |
#include <iostream>
class MyClass{
public:
static void staticFunction(){
std::cout << "Inside staticFunction" << '\n';
}
void nonstaticFunction(){
std::cout << "Inside nonstaticFunction" << '\n';
}
};
int main(){
/* call static function without an instance */
MyClass::staticFunction();
/* class static function from an instance (this is uncommon but valid) */
MyClass obj;
obj.staticFunction();
/* cannot call non-static function without an instance */
MyClass::nonStaticFunction(); /* Error cannot call non-static function
without instance */
/* call non-static function from an instance */
obj.nonstaticFunction();
return 0;
}
C++- 函数指针用法
#include <iostream>
int add(int a, int b);
int subtract(int a, int b);
int main(){
int(*operation)(int, int); /* declaration of function pointer */
operation = add; /* assign address of add function to operation */
printf("Addition result: %d\n", (*operation)(5, 3)); /* call function through function pointer */
operation = subtract; /* assign address of subtract function to operation */
printf("Subtract result: %d\n", (*operation)(5, 3)); /* call function through function pointer */
return 0;
}
int add(int a, int b){ return a + b; }
int subtract(int a, int b) { return a - b; }
C++一级配置器
template<int inst>
class __malloc_alloc_template {
private:
/* the below are the function
pointers which are used for cope with the out-of-memory(oom) */
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
/* allocator */
static void *allocate(size_t n) {
void *result = malloc(n); // primary allocator employs malloc() directly
/* when out of memory, invoke oom_malloc() */
if (0 == result) result = oom_malloc(n);
return result;
}
/* deallocator */
static void deallocate(void *p, size_t /* n */) {
free(p); /* primary allocator employs free() directly */
}
/* reallocator */
static void *reallocate(void *p, size_t /* old_sz */, size_t new_sz) {
void *result = realloc(p, new_sz);
/* primary allocator employs realloc() directly
when out of memory, invoke oom_realloc()*/
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
/* emulate set_new_handler(), which means that
out-of-memory handler is definable */
static void (*set_malloc_handler(void (*f)()))() {
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return (old);
}
};
/* malloc_alloc out-of-memory banding */
template<int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template<int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n){
void (* my_malloc_handler)();
void* result;
for(;;){ /* endlessly allocate and deallocate until allocate successfully */
my_malloc_handler = __malloc_alloc_oom_handler;
if(0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(* my_malloc_handler)();
result = malloc(n);
if(result) return result;
}
}
C++注: typedef __malloc_alloc_template<0> malloc_alloc;
此处inst
的值被指定为0
一级配置器主要采用 C 中的malloc()
, free()
, realloc()
的函数实现内存的 配置、释放、重配置操作,并实现仿 C++ 的new-handler
机制(因为此处并没有直接使用 ::operator new
来配置内存)
在 C++ 中 new handler
的实现机制:当系统无法满足内存配置需求时,可调用一个自己指定的函数。
换言之,当 operator::new
无法完成内存配置的操作时,在抛出异常前,会调用一个自己指定的 函数 new-handler 来妥协解决内存不足的问题。
注:
- SGI中用
malloc
而不是::operator new
来进行内存配置,因此需要实现一个类似 C++ 中set_new_handler()
的功能set_malloc_handler()
。 - SGI的一级配置器的
allocate()
和realloc()
都是在调用malloc()
和realloc()
不成功(发生内存不足等情况) 后才调用oom_malloc()
和oom_realloc()
,然后一直循环尝试配置和释放内存,直到内存配置成功为止,若内存配置始终不成功 那么oom_malloc()
和oom_realloc()
就会抛出__THROW_BAD_ALLOC
的 bad_alloc异常信息,或直接exit(1)
中止程序。 - 内存不足的问题的处理函数由程序的设计者完成。
2.6 第二级配置器 __default_alloc_template 剖析
二级配置器相较于以一级配置器多了一些额外的机制,减少了小型内存分配时所带 来的内存浪费(内存碎片),且分配的内存越小为后续带来的内存空间管理的难度就越大, 因为系统总要靠这多出来的空间进行内存管理。
SGI二级配置器的内存分配机制:
- 当分配的内存区块足够大时(大于128bytes),就转交给一级配置器处理。
- 当分配的内存区块较小时(小于128bytes),就通过内存池(memory pool)进行管理——层级管理法(sub-allocation)
层级管理法
每次配置一大块内存,并维护对应的自由链表(free-list)。下次弱再有相同大小的内存需求,直接从free-lists中进行 分配,如果程序释放了小型内存区块,那么就由配置器回收到free-lists中。
为了方便管理,SGI的二级配置器会主动将任何小额的内存需求量上调至 8 的倍数,并维护16个 free-lists,各自管理大小为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes 的小额内存区块。
free-lists
结构如下:
union obj{
union obj* free_list_link;
char client_data[1];
};
C++此处, union obj* free_list_link
可类比为链表中的 LinkList* next
, char client_data[1]
则用指向实际的内存区块,此种做法可以节省内存的开销。
补充:
struct
中的各个成员变量都有自己的内存空间union
中的各个成员变量共享着一块内存空间
二级配置器的部分实现
#include <cstddef>
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES / __ALIGN };
template<bool threads, int inst>
class __default_alloc_template{
private:
static size_t ROUND_UP(size_t bytes){ return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1)); }
/* '(bytes + __ALIGN -1': This part adds an offset to the 'bytes' value. The '__ALIGN - 1'
* is used to ensure that we round up to the next multiple of '__ALIGN'.For example, if '__ALIGN'
* is 4, then '__ALIGN - 1' is 3, and adding 3 ensures that the result will be at least a multiple
* of 4 greater than 'bytes'.
* '& !(__ALIGN - 1)‘: This part performs a bitwise AND operation wit the complement of '(__ALIGN - 4)'.
* The complement operation '~' flips all the bits of '(__ALIGN - 1)', effective creating a bitmask where
* all bits are set to 1 except for the lower bits determined by '__ALIGN - 1'. By performing a bitwise AND
* with this bitmask, we effectively set the lower bits to O, thus rounding down the result to the nearest
* multiple of '__ALIGN'.
*/
private:
union obj{
union obj* free_list_link;
char client_data[1];
};
private:
/* 16 free-lists */
static obj* volatile free_list[__NFREELISTS];
/* employ Nth free-list according to the size
* of memory chunk (begin with 1st memory chunk)
*/
static size_t FREELIST_INDEX(size_t bytes){ return (((bytes) + __ALIGN + 1) / __ALIGN - 1); }
/* return a object in size of n, and add other memory
* chunks in size of n into free-list if possible
*/
static void* refill(size_t n);
/* allocate a memory space that can hold n objs
* its capacity is size
* if inconvenient to allocate for n objs, n cloud decrease
*/
static void* refill(size_t size, int& nobjs);
// chunk allocation state
static char* start_free; // the start position in memory pool, only changes in chunk_alloc()
static char* end_free; // the end position in memory pool, only changes in chunk_alloc()
static size_t heap_size;
public:
static void* allocate(size_t n) { }
static void deallocate(void* p, size_t n) { }
static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};
/* the original value and definition setting for static data member */
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = 0;
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = 0;
template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
{0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0};
C++2.7 空间配置函数 allocate()
配置器的标准接口函数allocate(),其工作方式如下:
- 判断区块大小
- 大于128bytes调用一级配置器
- 小于128bytes就检查对应的free list
- 如果free list内有可用的区块,就直接用
- 如果free list内没有可用的区块,就将区块大小上调至8倍数bytes,然后调用refill(),准备为free list重新填充空间
// n must be > 0, to assure that
// there is the memory allocated
static void* allocate(size_t n){
obj* volatile* my_free_list;
obj* result;
// if allocating memory > 128 bytes
if(n > (size_t) __MAX_BYTES){
return (malloc_alloc:allocate(n));
}
// select a suitable chunk in 1 of 16 free lists
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == 0){
// no find a available free list
// preparing to refill another
void* r = refill(ROUND_UP(n));
return r;
}
// adjust free list
*my_free_list = result -> free_list_link;
return (result);
};
C++内存区块从free list调出的操作
2.8 空间释放函数 deallocate()
__default_alloc_template拥有一个标准接口函数deallocate(),其工作方式如下:
- 判断区块大小
- 大于128bytes,直接调用一级配置器
- 小于128bytes,找出对应的free list,将区块回收
// p can not be 0
static void deallocate(void* p, size_t n){
obj* q = (obj *)p;
obj* volatile* my_free_list;
// if size > 128 bytes, call the primary allocator
if(n > (size_t) __MAX_BYTES){
malloc_alloc::deallocate(p, n);
return;
}
// selecting the corresponding free list
my_free_list = free_list + FREELIST_INDEX(n);
// adjust free list, recycle the chunk
q -> free_list_link = *my_free_list;
*my_free_list = q;
}
C++内存区块回收至free list的操作
2.9 重新填充free lists
在free lists中没有可用的区块时,调用refill()以为free list重新填充空间, 新的空间从内存池(经由chunk_alloc()完成)取出:
- 当内存池中剩余的内存足够时,缺省取得20个新区块
- 当内存池中剩余的内存不足时,取得的新区块数可能小于20
// return a obj in size of n
// and supply some chunks for free list properly sometimes
// supposing that n is upregulated to a multiple of 8
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){
int nobjs = 20;
// call chunk_alloc(), try to get n(objs) chunks
// as new nodes for free list
char* chunk = chunk_alloc(n, nobjs); // nobjs -> pass by reference
obj* volatile* my_free_list;
obj* result;
obj* current_obj, * next_obj;
int i;
// if only get one chunk, then allocate this chunk to the target
// so there is no new node for free list
if(l == nobjs) return(chunk);
// if not, adjust free list and prepare to link a new node
my_free_list = free_list + FREELIST_INDEX(n);
// create free list in chunk space
result = (obj*)chunk; // this piece of chunk will return to user
// help free list point toward the new allocated space (from memory pool)
*my_free_list = new_obj = (obj*)(chunk + n);
// connect the each node in free list
for(i = 1; ; i++){ // i begin with 1, because i[0] will be return to user
current_obj = next_obj;
if (nobjs - 1 == i){
current_obj -> free_list_link = 0;
break;
}else{
current_obj -> free_list_link = next_obj;
}
}
return(result);
}
C++2.10 内存池 memory pool
在谈及到refill()
时,提到了关于chunk_alloc()
这个函数, 它是用来从内存池中取空间给free list。
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs){
char* result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; // the rest of memory pool
if(bytes_left >= total_bytes){
// the rest of memory pool could satisfy the need
result = start_free;
start_free += total_bytes;
return(result);
}else if( bytes_left >= size){
// the rest of memory pool could not totally satisfy the need
// but only one or more chunks
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
}else{
// memory pool can not supply the size o only one chunk
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// make full use of memory fragments
if(bytes_left > 0){
// allocate some surplus memory for free list primarily
// select the proper free list
obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);
// adjust free list, integrate the surplus memory in memory pool
((obj*) start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj*) start_free;
}
// configure heap to supply memory pool
start_free = (char*) malloc(bytes_to_get);
if(0 == start_free){
// heap is not enough, malloc() fails
int i;
obj* volatile* my_free_list, *p;
// check the memory that I currently have
// allocate the small memory space is dangerous under multi-threads circumstance
// select a proper free list
// "proper" means that the unused memory is big enough to satisfy the need
for(i = size; i <= __MAX_BYTES; i += __ALIGN){
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if(0 != p){
// chunk not in free list
// adjust free list to release the unused memory
*my_free_list = p -> free_list_link;
start_free = (char*) p;
end_free = start_free + i;
// revoke itself to fix nobjs
return(chunk_alloc(size, nobjs));
// any surplus memory will be integrated in free list as spare
}
}
end_free = 0; // if occur the accident, allocate the primary allocator
// turning to out-of-memory
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
// if failed, throw exception
// if succeeded, memory lack will be fixed
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
// revoke itself to fix nobjs
return(chunk_alloc(size, nobjs));
}
C++chunk_alloc()
函数通过end_free - start_free
来判断内存中的内存余量:
- 如果内存足够,就直接调出20个区块返回给free list
- 如果内存不足
- 但够满足一个及以上区块,就调出(不足20个)剩余的区块
- 甚至连一个区块都无法调出,此时尝试使用
malloc()
从heap中配置内存来增加内存池中的内存余量,配置的内存大小随着配置的次数逐渐增加
举例:
- 当调用
chunk_alloc(32, 20)
时,于是malloc()
配置40个32bytes区块, 取出其中的第一个区块,剩下的19个放入free_list[3]
进行维护,再将剩余的20个 留给内存池 - 当再调用
chunk_alloc(64, 20)
时,此时free_list[7]
空空如也, 而内存池中的内存余量20 * 32 bytes / 64 bytes = 10个,就先把这10个区块返回, 取出其中的第一个区块,剩下的9个放入free_list[7]
中进行维护。此时内存池空空如也 - 再继续调用
chunk_alloc(96, 20)
,此时free_list[11]
空空如也,此时想要从内存池中找内存, 然而内存池中也是空空如也,于是以malloc()
配置40 + n (附加量)个96bytes区块,取出其中的第一个区块, 再将19个交给free_list[11]
进行维护,剩下的20+n (附加量)留给内存池…… - 当整个system heap空间都不够了,以至于无法再继续向内存池中添加内存,
malloc()
就不无法继续进行,chunk_alloc()
再在free list中寻找是否有可用且足够大的区块,有就用,没有就找一级配置器帮忙, 一级配置器使用malloc()
进行内存配置,但它有out-of-memory处理机制(类似于new handler
):- 如果成功,释放出足够的内存以使用
- 如果失败,抛出
bad_alloc
异常
提供标准配置接口的 simple_alloc
template<class T, class Alloc>
class simple_alloc{
public:
static T* allocate(size_t n){
return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));
}
static T* allocate(void){
return (T*) Alloc::allocate(sizeof(T));
}
static void deallocate(T* p, size_t n){
if(0 != n) Alloc::deallocate(p, n * sizeof(T));
}
static void deallocate(T* p){
Alloc::deallocate(p, sizeof(T));
}
};
C++SGI通常使用这种方式来使用配置器:
template <class T, class Alloc = alloc> // 缺省使用 alloc 为配置器
class vector{
public:
typedef T value_type;
protected: // 专属配置器,每次配置一个元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
};
C++2.11 内存基本处理工具
STL定义有5个全局函数,作用于未初始化空间上:
construct()
-> 构造destroy()
-> 析构uninitialized_copy()
->copy()
uninitialized_fill()
->fill()
uninitialized_fill_n()
->fill_n()
其中 copy()
, fill()
, fill_n()
都为STL算法
uninitialized_copy()
template<class InputIterator, class ForwardIterator>
ForwardIterator
unitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result);
C++uninitialized_copy()
将内存的配置与对象的构造分离开来,其工作方式:在输入范围内,利用迭代器i
,该迭代器会调用 construct(&*(result + (i - first)), *i)
,以此来产生*i
的拷贝对象,并将拷贝得到的对象放置到输出范围的相对位置上。
当要实现一个容器时, uninitialized_copy()
可以帮助容器的全区间构造函数在配置内存区块(以包含范围内的所有元素)后,在该内存区块上构造元素。
C++对于此还有一个要求——commit or rollback :若能对每个元素都成功能进行uninitialized_copy()
,则commit ,否则rollback。
uninitialized_fill
template<class ForwardIterator, class T>
void unintialized_fill(ForwardIterator first, ForwardIterator last,
const T&x);
C++uninitialized_fill()
将内存配置与对象的构造分离开来,其工作方式:对于输入范围内的每个迭代器i
,调用 construct(&*i, x)
,在i
所指之处放置x的拷贝对象。
C++对此同样也有commit or rollback的要求:若能对每个元素都能成功进行uninitialized_fill()
,则commit ,如果有一个copy constructor抛出异常(操作失败), 则将所有成功产生的元素全部析构掉。
uninitialized_fill_n
template<class ForwardIterator, class Size, class T>
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
C++uninitialized_fill_n()
将内存配置与对象的构造分离开来,它可以为指定范围内的所有元素设定相同的初值。 对于[first, first + n]
范围内的每个迭代器i
, uninitialized_fill_n()
会调用construct(&*i, x)
,为其在对应的位置上产生x
的拷贝对象。
C++对此同样也有commit or rollback的要求:若能对每个元素都能成功uninitialized_fill_n()
,则commit ,如果有一个copy constructor抛出异常(操作失败), 则将所有成功产生的元素全部析构掉。