Extra Cookie

Yet Another Programmer's Blog

STL 源码分析-A.万物起源-2

在分析了对象的构建和析构之后,我们接着看对象构建所基于的内存空间是如何分配和释放的。这一功能是由 stl_alloc 提供的。之前提到过 allocate,在 SGI STL 中是不使用的,因为其只是对 new 和 delete 进行了简单的封装,并且加上了这段代码

1
set_new_handler(0);

这个函数用来指定如果内存分配失败时的 callback 函数,定义如下

1
2
typedef void (*new_handler)();
new_handler set_new_handler(new_handler p) throw();

使用时参数传入 NULL(0) 则表示卸除 new_handler,也就意味着如果 ::operator new 分配内存失败,则会抛出 std::bad_alloc 类型的异常。

而 SGI STL alloc 的实现则考虑到了内存不足时该如何应变,以及小区域频繁的分配可能造成的内存碎片问题。并且,没有使用 C++ 内存分配的基本方法 ::operator new::operator delete,而使用 malloc()free() (在对象的构建和析构中采用的时 placement new),一个估计是因为历史原因,另一个是需要实现 realloc 操作,而 new()delete() 并不支持。

alloc 被设计为两级,第一级直接使用 malloc()free() 来进行内存分配和释放,第二级则有不同策略,如果需分配空间大于 128 bytes,则认为足够大,直接使用第一级方法进行分配,反之,则认为足够小,使用内存池来进行分配以减少额外负担。这两级是并列的关系,可以选择只开放第一级,也可以同时开放两级,通过宏 __USE_MALLOC,如下

1
2
3
4
5
6
7
8
9
10
11
12
13
...
typedef __malloc_alloc_template <0> malloc_alloc;
...
# ifdef __USE_MALLOC
typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;
# else
...
template
class __default_alloc_template {
...
#endif
...

__malloc_alloc_template 是第一级 alloc,__default_alloc_template 则是第二级 alloc。先从前者着手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static void* allocate(size_t __n)
{
    // 直接使用 malloc
    void* __result = malloc(__n);
    // 如果分配失败,执行
    if (0 == __result) __result = _S_oom_malloc(__n);
    return __result;
}

static void deallocate(void* __p, size_t /* __n */)
{
    // 直接使用 free
    free(__p);
}

// 类似 allocate
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
    void* __result = realloc(__p, __new_sz);
    if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
    return __result;
}

// 模拟前面提到的 C++ 中的 set_new_hanlder(),用来指定内存分配失败后的处理函数
static void (* __set_malloc_handler(void (*__f)()))()
{
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
}

这三个函数是类 __malloc_alloc_template 提供的三个 public 接口,外界可以通过它们来完成内存的分配,释放,重新分配,以及设定内存失败时的处理方法。

deallocate() 仅仅只是封装 free()allocate()reallocate() 中,在内存分配失败时,会继续执行 _S_oom_malloc()_S_oom_realloc(),后者跟前者基本处理方法一致,除了 realloc()alloc() 之分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template
void*
__malloc_alloc_template <__inst> ::_S_oom_malloc(size_t __n)
{

    // 用来接收用户指定的分配失败处理函数
    void (* __my_malloc_handler)();
    void* __result;

    // 不断尝试分配失败解决方案,并再次分配
    for (;;) {
        // 指定分配失败处理函数
        __my_malloc_handler = __malloc_alloc_oom_handler;
        // 如果处理函数为空,直接抛出异常
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
        // 执行处理函数,比如释放其他内存
        (*__my_malloc_handler)();
        // 再次 malloc
        __result = malloc(__n);
        if (__result) return(__result);
    }
}

为了能够符合 STL 规范,定义 simple_alloc 类,用来包装整个 alloc 的实现。使用时只需指定相应的 alloc 类型,便可直接使用该包装类。可以看到,内存分配从传入所需空间字节数变成了需分配某元素的个数。SGI STL 容器全都使用的是这个包装类,如 vector。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template
class simple_alloc {
public:
    static _Tp* allocate(size_t __n)
      { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
    static _Tp* allocate(void)
      { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
    static void deallocate(_Tp* __p, size_t __n)
      { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
    static void deallocate(_Tp* __p)
      { _Alloc::deallocate(__p, sizeof (_Tp)); }
};

// 如果没有指定 __STL_USE_STD_ALLOCATORS 时使用,反之使用缺省 allocate(defalloc.h)。
template
class _Vector_base {
...
  typedef simple_alloc <_tp , _Alloc> _M_data_allocator;
  _Tp* _M_allocate(size_t __n)
    { return _M_data_allocator::allocate(__n); }
  void _M_deallocate(_Tp* __p, size_t __n)
    { _M_data_allocator::deallocate(__p, __n); }
};

template
class vector : protected _Vector_base < _tp , _Alloc>
{
...
};

本文代码示例基于 SGI STL 3.2。

下一篇将分析 alloc 考略内存碎片的实现方式。

Comments