Java教程

SGI STL源码 空间配置器

本文主要是介绍SGI STL源码 空间配置器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 空间配置器
    • 基本概念
    • 空间配置器的标准接口
    • 两种空间配置器
      • 空间配置器的职责
    • 配置器allocator文件说明
    • 构造和析构工具:construct, destroy
    • 空间配置与释放,std::alloc
    • 第一级配置器:__malloc_alloc_template
      • 一级配置器实现
    • 第二级配置器:__default_alloc_template
      • 自由链表 free-lists
      • __default_alloc_template 的数据结构
      • ROUND_UP() 向上调对齐
      • FREELIST_INDEX() 找合适槽位
      • allocate() 空间配置
      • deallocate() 空间释放
      • refill() 重新填充free list
      • memory pool 内存池

空间配置器

基本概念

为什么叫allocator空间配置器,而不叫内存配置器?
因为空间不一定是内存,也可能是磁盘或其他辅助存储介质。可以写一个allocator,直接向硬盘取空间。

不过,实际上,我们最常用的就是用于配置内存。

空间配置器的标准接口

allocator标准接口:

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
allocator::rebind
    一个嵌套的(nested)class template。class rebind<U> 拥有唯一成员other, 那是一个typedef, 代表allocator<U>.
allocator::allocator()
    default constructor
allocator::allocator(const allocator&)
    copy constructor
template<class U> allocator::allocator(const allocator<U>&)
    泛化的copy constructor
allocator::~allocator()
    default constructor
pointer allocator::address(reference x) const
    返回某个对象的地址. 算式a.address(x)等同于&x
const_pointer allocator::address(const_reference x) const
    返回某个const对象的地址. 算式a.address(x)等同于&x
pointer allocator::allocate(size_type n, const void* = 0)
    配置空间, 足以存储n个T对象. 第二参数是个提示. 实现上可能会利用它来增进区域性(locality), 或完全忽略之
void allocator::deallocate(pointer p, size_type n)
    归还先前配置的空间
size_type allocator::max_size() const
    返回可成功配置的最大量
void allocator::construct(pointer p, const T& x)
    等同于 new ((const void*)p) T(x)
void allocator::destroy(pointer p)
    等同于p->~T()

两种空间配置器

SGI STL有2个种空间配置器:
1)std::allocator,符合STL标准,但很少使用,也不建议使用。因为只是把::operator new和::operator delete做了一层薄薄封装,效率差。
2)std::alloc,SGI特殊空间配置器,将配置器分为两级,兼顾了效率与内存碎片问题,效率高。推荐使用。

下面主要讲的也是std::alloc。

空间配置器的职责

通常,我们习惯用new、delete对C++ 内存配置进行申请、释放操作。比如,

class Foo {...}
Foo* pf = new Foo;
delete pf;

其中,new操作内含2阶段操作:
1)调用::operator new配置内存。
2)调用Foo::Foo()构造对象。

delete操作也内含2阶操作:
1)调用Foo::~Foo()析构对象;
2)调用::operator delete释放内存;

而STL的allocator(空间配置器)把这两阶段操作分开了。其中,内存配置(申请)由alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由全局::construct()负责,对象析构由全局::destroy()负责。

配置器allocator文件说明

STL标准规定,配置器定义于<memory>,而SGI <memory>内含3个与配置器相关的文件:
1)<stl_construct.h> 定义了全局函数construct(), destroy(), 负责对象的构造和析构。隶属于STL标准规范。
2)<stl_alloc.h> 定义了一、二级配置器,彼此合作。配置器名为alloc。
3)<stl_uninitialized.h> 定义一些全局函数,用来填充(fill)或复制(copy)大块内存数据。都属于STL标准规范:

  • un_initialized_copy()
  • un_initialized_fill()
  • un_initialized_fill_n()
    3个函数不属于配置器范畴,但与对象初值设置有关。对于容器的大规模元素初值设置很有帮助。这些函数对于效率都有面面俱到的考虑,最差情况下会调用construct()。最佳情况则会使用C标准函数memmove()直接进行内存数据的移动。

构造和析构工具:construct, destroy

全局函数construct(), destroy()在已配置内存的基础上,用于对象的构造和析构
因此,construct()需要原生内存(native memory)地址和要构造对象类型,可能包含初值(列表)用于构造对象作为参数。
destroy有两种形式:1)析构单个对象,提供对象指针即可;2)析构迭代器区间所有对象,提供迭代器区间[first, last)。

注意:如果是原始类型区间,如char* [start, end),则不需要析构,因为没有构建对象。

可以得到construct和destroy的模板函数:

// <stl_construct.h>

template <class T>
inline void _Construct(T1* p) {
  new ((void*) p) T(); // placement new; 调用T::T()
}

template<class T1, class T2>
inline void construct(T1* p, const T2& value) {
       new (p) T1(value); // placement new; 调用T1::T1(value)
}

// destroy()第一个版本, 接受一个指针
template<class T>
inline void destroy(T* pointer) {
       pointer->~T(); // 调用dtor ~T()
}

// destroy()第二个版本, 接受两个迭代器. 次函数设法找出元素的数值型别,
// 进而利用__type_traits<>求取最适当措施
template<class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
       __destroy(first, last, value_type(first));
}

// 判断元素的数值型别(value type)是否有trivial destructor
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());
}

// 如果元素的数值型别(value type)有non-trivial destructor, 则派送(dispatch)到这里
template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last,  __false_type) {
       for (; first < last; ++first)
              destroy(&*first);
}

// 如果元素的数值型别(value type)有trivial destructor, 则派送(dispatch)到这里
template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last,  __true_type) {
}

// destroy() 第二版针对迭代器为char*和wchar_t*的特化版
// 原生指针区间不需要析构, 因为没有对象, 类似地,还有int*, long*, float*, double*,这里省略
inline void destroy(char*, char*) { }
inline void destroy(wchar_t*, wchar_t*) { }

代码中一组__destroy()是辅助实现destroy()的,编译器会在编译期根据萃取出参数的类型(value type)。接着萃取出trivial_destructor特性,判断是否支持trivial_destructor(平凡的析构函数,说明没有申请动态内存),如果支持(特性为__true_type),就不需要专门调用析构函数;如果不支持(特性为__false_type),就需要针对迭代器区间每个元素,逐个调用析构函数。
如果迭代器区间包含元素较多,这能节省不少时间。

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

std::alloc 负责内存的配置和释放。对象构造前的空间配置和对象析构后的空间释放,由<stl_alloc.h>负责,SGI对此设计哲学:

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

本文为控制问题复杂度,以下讨论及源码,皆排除多线程。

C++的内存配置基本操作::operator new(),内存释放基本操作 ::operator delete()。这2全局函数相当于C的malloc()和free()。SGI正是以malloc()和free()完成内存的配置与释放的,但SGI STL的std::alloc不能使用operator new/delete,因为new/delete会直接构造/析构对象,而这不符合std::alloc职责。

std::alloc设计基本思想
为避免小型区块可能造成的内存碎片问题,SGI STL设计了双层级配置器:
1)第一级配置器,直接使用malloc(), free();
2)第二级配置器,视情况采用不同策略:
当配置区块 > 128bytes时,视为“足够大”,便调用第一级配置器;
当配置区块 <= 128bytes时,视为“过小”,交给memory pool(内存池)来管理,不再求助于第一级配置器。

设计可以只开放第一级配置器,可以同时开启。取决于__USE_MALLOC是否被定义(SGI STL并未定义__USE_MALLOC)。

SGI STL的两级配置器:__malloc_alloc_template是第一级配置器,__default_alloc_template是第二级配置器。alloc不接受任何template型别参数。并且,SGI还在此基础上,用simple_alloc包装了一个接口,对用户屏蔽内部细节,使之符合STL规格。

// <stl_alloc.h>

// 内部4个成员函数都是单纯的转发调用
template<class T, class Alloc>
class simple_alloc { // simple_alloc包装第一级配置器和第二级配置器, 用户传入模板参数给Alloc即可
public:
       static T* allocate(size_t n) { // 配置n个单位T类型对象的原始空间
              return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T));
       }
       static T* allocate(void) {     // 配置1个单位T类型对象的原始空间
              return (T*)Alloc::allocate(sizeof(T));
       }
       static void deallocate(T* p, size_t n) { // 释放n个单位T类型对象的原始空间
              if (0 != n) Alloc::deallocate(p, n * sizeof(T));
       }
       static void deallocate(T* p) { // 释放1个单位T类型对象的原始空间
              Alloc::deallocate(p, sizeof(T));
       }
};

除了转发调用,simple_alloc包装配置器还将接口的配置单位,由byte转换成了元素的大小(sizeof(T))。SGI STL容器全部使用这个simple_alloc接口。
例如,vector的专属空间配置器data_allocator,就是simple_alloc<value_type, Alloc>,当然Alloc取决于我们传入vector的配置器类型(一级或二级),缺省是std::alloc。

template<class T, class Alloc = alloc> // 使用缺省alloc为配置器
class vector {
...
protected:
       // 专属空间配置器, 每次配置一个元素大小
       typedef simple_alloc<value_type, Alloc> data_allocator;

       void reserve(size_t n) {
              if (...)
                     data_allocator::deallocate(start, end_of_storage - start);
       }
       // ...
};

第一级配置器:__malloc_alloc_template

  1. allocate() 直接使用malloc(), deallocate() 直接使用free();
  2. 模拟C++的set_new_handler()以处理内存不足的状况。

set_new_handler只有针对placement new申请内存时,才有效;用malloc申请时,无效。需要借助malloc返回值为空,进行申请内存失败判断。

如何选择使用哪个配置器?
定义或取消宏__USE_MALLOC,就能决定alloc的实际类型(一级配置器 or 二级配置器)。SGI STL并未定义__USE_MALLOC,因此SGI默认使用的二级配置器。

# ifdef __USE_MALLOC

typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;

# else
...
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef __default_alloc_template<false, 0> single_client_alloc;
...
#endif

一级配置器实现

用malloc(), free(), realloc()等C函数执行实际的内存配置、释放、重新配置,并模拟实现类似于C++ new-handler异常处理机制。不能直接使用new-handler机制,因为并没有用::operator new配置内存,而是用的malloc。

C++ new handler机制是什么?
指你可以要求系统在内存配置需求无法被满足时,调用一个你指定的函数,来进行异常处理。i.e. 一旦::operator new无法完成任务,在抛出std::bad_alloc异常前,会先调用由客户端指定的处理例程。 (见《Effective C++》条款49)

谁负责注册、设计“内存不足处理例程”?
设计“内存不足处理例程”是客户端的责任,注册“内存不足处理例程”也是客户端的责任。也就是,客户负责调用set_malloc_handler()注册内存不足处理例程,并定义传入实参(内存不足如何处理)。

// <stl_alloc.h>

// 第一级配置器
// 用于异常处理
#ifndef __THROW_BAD_ALLOC
#  if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)
#    include <stdio.h>
#    include <stdlib.h>
#    define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
#  else /* Standard conforming out-of-memory handling */
#    include <new>
#    define __THROW_BAD_ALLOC throw std::bad_alloc()
#  endif
#endif

// malloc-based allocator 通常比default alloc速度慢
// 一般而言是thread-safe, 并且对空间的运用比较高效(efficient)
// 以下是第一级配置
// 注意, 无"template型别参数". 至于"非型别参数"inst, 则完全没派上用场
template<int inst>
class __malloc_alloc_template {

private:
       // 以下都是函数指针, 所代表的函数将用来处理内存不足的情况
       // oom: out of memory.
       static void *oom_malloc(size_t);            // 模拟C++ placement new, 不断尝试配置内存, 调用客户注册的处理例程或抛出异常
       static void *oom_realloc(void*, size_t);    // 模拟C++ placement new, 不断尝试重新配置内存, 调用客户注册的处理例程或抛出异常
       static void(*__malloc_alloc_oom_handler)(); // 保存客户注册的 内存不足处理例程

public:
       static void *allocate(size_t n) {
              void *result = malloc(n); // 第一级配置器直接使用malloc()
              // 以下无法满足需求时, 改用oom_malloc()
              if (0 == result) result = oom_malloc(n);
              return result;
       }

       static void deallocate(void* p, size_t /*n*/) {
              free(p); // 第一级配置器直接使用free()
       }

       static void *reallocate(void* p, size_t /* old_sz */, size_t new_sz) {
              void *result = realloc(p, new_sz); // 第一级配置器直接使用realloc()
              // 以下无法满足需求时, 改用oom_realloc()
              if (0 == result) result = oom_realloc(p, new_sz);
              return result;
       }

       // 以下仿真C++的set_new_handler(). 换句话说, 你可以通过它指定自己的out-of-memory handler
       // 注册 内存不足处理例程
       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 handling
// 初值0, 有待客户端设定
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 (; ;) { // 循环尝试配置内存
        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;
    }
}

template<int inst>
void* __malloc_alloc_template<inst>::oom_realloc(void* p, size_t n) {
    void(*my_malloc_handler)();
    void* result;
    for (; ;) { // 循环不断尝试释放、配置 ...
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { // 如果客户没有设置my_malloc_handler, 就抛出异常
            __THROW_BAD_ALLOC;
        }
        (*my_malloc_handler)();    // 调用客户注册的处理例程, 企图释放内存
        result = reallocate(p, n); // 尝试重新配置内存
        if (result) {
            return result;
        }
    }
}

// 注意, 以下直接将参数inst指定为0
typedef __malloc_alloc_template<0> malloc_alloc;

第二级配置器:__default_alloc_template

与第一级配置器区别:为避免太多小额区块造成内存碎片,多了一些机制。

SGI第二级配置做法:如果区块够大,> 128bytes,移交给第一级配置器处理;当区块 < 128bytes,则以内存池(memory pool)管理。
这种方法称为次配置(sub-allocation):每次配置一大块内存,并维护对应自由链表(free-list)。下次再有相同大小内存需求时,就直接从free-lists中取出。如果客户端归还小额区块,就由配置器回收到free-lists中。
简而言之,二级配置器负责内存配置、回收,会根据区块大小,选择自行配置,还是移交给一级配置器处理。

因此,可以知道二级配置器多了自由链表和内存池两个机制,专门为处理 <= 128bytes的内存申请而生。

自由链表 free-lists

二级配置器的核心之一就是free-lists(自由链表),每个free-list代表一类空闲区块,大小从8,16,24,...,到128 (bytes),共16个。16个free-list的头结点,用一个数组free_list[16]表示,下文称之为槽位。每个槽位指向的区块是一个链表,而该区块就是链表的第一个空闲块。

free-list的精髓就是联合体obj:

    // free-lists节点结构
    union obj {
        union obj* free_list_link;
        char client_data[1]; /* The client sees this. */
    };

一般情况下,我们用next 和 data的struct来描述链表节点,而obj用obj*的union,这是为什么?*
因为这样可以节省维护链表的指针空间。一个区块,在分配给客户端之前,首部大小为obj那部分可以看作一个指针free_list_link,用来串成链表;而分配给客户端之后,这部分无需当做指针,可以被客户按需使用;待客户归还区块时,首部大小为obj那部分又会被当做指针,用来串成链表,加入free list。
free_list_link所指向的内存区块大小,由链表头结点,即槽位所在free_list[]中的索引决定。而归还时,调用者会记录区块大小。因此,obj不需要额外存储区块大小。

为什么free-list区块最小尺寸是8byte,而不是4byte?
因为64位系统上,指针尺寸8byte;32位系统上,指针尺寸4byte。为了兼容32位、64位系统,取较大值8。

下图是以96byte区块为例,描述free-lists结构:

__default_alloc_template 的数据结构

SGI STL中,__default_alloc_template 的数据结构签名如下:

// 第二级配置器的部分实现内容
enum { __ALIGN = 8 }; // 小型区块上调边界
enum { __MAX_BYTES = 128 }; // 小型区块的上限
enum { __NFREELTISTS = __MAX_BYTES / __ALIGN }; // free-lists个数

// 以下是第二级配置器
// 注意, 无"template型别参数", 且第二参数完全没派上用场
// 第一参数用于多线程环境. 本书不讨论多线程环境
template<bool threads, int inst>
class __default_alloc_template {
private:
       // ROUND_UP() 将bytes上调至8的倍数
       static size_t ROUND_UP(size_t bytes);

private:
       // free-lists节点结构
       union obj {
              union obj* free_list_link;
              char client_data[1]; /* The client sees this. */
       };

private:
       // 16个free-lists
       static obj* volatile free_list[__NFREELTISTS];

       // 以下函数根据区块大小, 决定使用第n号free-lists. n从1起算
       // 根据要申请的内存空间大小(bytes), 找到free list中不小于bytes的区块, 返回其位于free_list[]的编号
       // e.g. 1) bytes = 96, return = (96 + 8 - 1) / 8 - 1 = 11
       // 2) bytes = 95, return = (95 + 8 - 1) / 8 - 1 = 11
       // 3) bytes = 97, return = (97 + 8 - 1) / 8 - 1 = 12
       static size_t FREELIST_INDEX(size_t bytes);
       static void *refill(size_t n);
       // 配置一大块空间, 可容纳nobjs个大小为"size"的区块
       // 如果配置nobjs个区块有所不便, nobjs可能会降低
       static char* chunk_alloc(size_t size, int &nobjs);

       // Chunk allocation state
       static char* start_free; // 内存池起始位置. 只在chunk_alloc()中变化
       static char* end_free;   // 内存池结束位置. 只在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);
};

关于free-lists,有两个重要操作:
1)ROUND_UP() 将参数bytes上调至8的倍数,确保所有操作都是8byte对齐;
2)FREELIST_INDEX() 根据参数bytes,在free_list[]中找到合适的槽位:确保区块大小 >= bytes。

ROUND_UP() 向上调对齐

ROUND_UP()实现如下:

       // ROUND_UP() 将bytes上调至8的倍数
       static size_t ROUND_UP(size_t bytes) {
              return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
       }

FREELIST_INDEX() 找合适槽位

FREELIST_INDEX()实现如下:

       // 以下函数根据区块大小, 决定使用第n号free-lists. 
       // 根据要申请的内存空间大小(bytes), 找到free list中不小于bytes的区块, 返回其位于free_list[]的编号
       // e.g. 1) bytes = 96, return = (96 + 8 - 1) / 8 - 1 = 11
       // 2) bytes = 95, return = (95 + 8 - 1) / 8 - 1 = 11
       // 3) bytes = 97, return = (97 + 8 - 1) / 8 - 1 = 12
       static size_t FREELIST_INDEX(size_t bytes) {
              return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
       }

allocate() 空间配置

作为一个配置器,最核心的功能莫过于分配内存、回收内存。allocate()负责分配内存,deallocate()负责回收内存。

利用allocate()申请n bytes内存流程:

有3个关键点:
1)申请内存空间n > 128bytes时,交给一级配置器处理。而一级配置器的__malloc_alloc_template<>::allocate()在前面已讲过,这里不再遨述。
2)n <= 128bytes,在free_list[]数组会找一个适当的区块链表free list,并且该free list有可用空间时,需要将free list链表的第一个空闲数据块交给客户,而自身的指针也同样需要更新。
3)在2)的基础上,free list并没有可用空间时,就会调用refill()重新填充该free list。这部分放到下面的refill()函数部分讲解,而内部涉及到memory pool(内存池)的部分,放到下面memory pool部分专门讲解。

什么时候表示free list有空闲区块?
free_list[i](i=0,1,..15)的free_list_link所指向的下一个链表节点如果非空(非0),代表有空闲区块。而二级指针my_free_list指向free_list[i](某个槽位)。

针对情形2),当free list由空闲区块时,拔出第一个空闲区块给客户

二级配置器的allocate()源码:

// n must be > 0
static void * allocate(size_t n) {
       obj* volatile* my_free_list;
       obj* result;

       // >128, 调用第一级配置器
       if (n > (size_t)__MAX_BYTES) {
              return (malloc_alloc::allocate(n)); // malloc_alloc即一级配置器 __malloc_alloc_template<0>
       }

       // 寻找16个free lists中适当的一个
       my_free_list = free_list + FREELIST_INDEX(n);
       result = *my_free_list;

       if (result == 0) {
              // 没找到可用的free list, 准备重新填充free list
              void *r = refill(ROUND_UP(n)); /* 后面详述 */
              return r;
       }

       // 调整free list
       *my_free_list = result->free_list_link;
       return (result);
}

deallocate() 空间释放

空间释放与空间配置的逆过程,由deallocate()处理,负责回收分配出去的内存空间。总的原则是谁配置的空间,由谁来负责回收。

不过,与allocate()分配空间不同,deallocate()只有2个关键点,因为不存在内存空间不够的情况。
2个关键点:
1)回收的空间 n > 128byte时,交给第一级配置器处理;
2)n <= 128bytes时,找到适当的free list,然后调整free list,将回收空间加入其中。

二级配置器回收空间流程:

二级配置器回收空间结构变化示意图:

二级配置器deallocate()源码:

// p 不可以是0
static void  deallocate(void* p , size_t n) {
       obj* q = (obj*)p;
       obj* volatile *my_free_list;

       // > 128调用第一级配置器
       if (n > (size_t)__MAX_BYTES) {
              malloc_alloc::deallocate(p, n);
              return;
       }

       // 寻找对应free list
       my_free_list = free_list + FREELIST_INDEX(n);
       // 调整free list, 回收区块
       q->free_list_link = *my_free_list;
       *my_free_list = q;
}

可以看到,当 归还空间大小 <= 128时,deallocate并没有将空间归还给系统,而是交给了free list,方便下次申请。这样可以有效避免内存碎片问题。

refill() 重新填充free list

在allocate()中,当发现合适的free list中并没有可用的空闲块时,就会调用refill()为free list重新填充空闲空间。新空间由chunk_alloc()完成,默认取自内存池。

refill() 默认向chunk_alloc()申请nobjs=20个大小为n(假定n已经调整为8倍数)的(连续)内存空间,当然实际成功申请到多少个,需要根据实际情况决定,可通过nobjs传出值判断。可以肯定的是,如果有返回值(没有出现异常终止程序),那么至少会有一个大小为n的对象。
refill()会得到一个连续空间,而把第一个大小n的对象返回给客户;至于剩余的空间,在按尺寸n找到合适的free list后,将剩余空间按链表形式加入free list。

refill() 重新填充free list流程:

refill()源码:

// 返回一个大小为n的对象, 并且有时候会为适当的free list增加节点
// 假设n已经适当上调至8的倍数
template<bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n) {
       int nobjs = 20;

       // 调用chunk_alloc(), 尝试取得nobjs个区块作为free list的新节点
       // 注意参数nobjs是pass by reference
       char* chunk = chunk_alloc(n, nobjs); // 下节详述
       obj* volatile *my_free_list; // 2级指针, 指向free list链表头结点, 也位于free_list[]槽位上
       obj* result;
       obj *current_obj, *next_obj;
       int i;

       // 如果只获得一个区块, 这个区块就分配给调用者, free list无新节点
       if (1 == nobjs) return (chunk);

       // 否则准备调整free list, 纳入新节点
       my_free_list = free_list + FREELIST_INDEX(n);

       // 以下在chunk空间内建立free list
       result = (obj*)chunk; // 首部这一块准备返回给客户端

       // 以下引导free list指向新配置的空间(取自内存池)
       *my_free_list = next_obj = (obj*)(chunk + n);

       // 以下在chunk剩余空间(除去返回给客户的首部)上, 将free list的各节点串起来
       for (i = 1; ; ++i) { // 从1开始, 因为第0个将返回给客户端
              current_obj = next_obj;
              next_obj = (obj*)((char*)next_obj + n);
              if (nobjs - 1 == i) {
                     current_obj->free_list_link = 0;
                     break;
              }
              else {
                     current_obj->free_list_link = next_obj;
              }
       }

       return (result);
}

memory pool 内存池

二级配置器的另一个核心就是memory pool(内存池)。它的作用就是,每次refill() free list的时候,会把多申请的空间(默认申请20个大小n对象空间,而只给客户1个对象)交给内存池管理。

那么,内存池是如何管理这些内存的呢?
内存池管理内存的核心在于,通过chunk_alloc()向客户提供内存配置。chunk_alloc()需要2个参数:一个对象的大小为size(bytes,假设已经调整至8的倍数),一个需要申请的对象个数nobjs(注意这是个引用类型,是个结果参数)。
内存池自身通过两个指针边界管理,start_free ~ end_free;而heap_size,表示总的向OS成功申请到的内存总量。

需求的内存总量 total_bytes为size * nobjs,内存池剩余空间bytes_left为 end_free - start_free

由于这块比较复杂,我们分情况讨论。
1)当内存池剩余空间 >= 需求内存总量时,直接从内存池划扣(移动start_free 边界)。

2)当内存池剩余空间不能完全满足需求量,但足够供应一个(含)以上的区块需求。
我们知道,客户(refill())通过chunk_alloc()申请内存的时候,实际上只需要一个区块,但会默认申请20个区块。也就是说,实际上最少只供应一个也能满足需求。但我们还是让内存池尽量满足客户需求,分配尽量多的区块数nobjs = bytes_left / size。这样,实际供应的总量为size*nobjs。
同样地,从内存池划扣空间需要移动start_free边界。

3)当内存池剩余空间连一个区块都不能满足时,可能需要向OS申请内存(调用malloc())。
3.1)向OS申请内存时,申请空间bytes_to_get为2 * total_bytes + ROUND_UP(heap_size >> 4),而并不是直接只申请total_bytes,这样做的目的,是为了让内存池拥有多余的、与本次申请内存总量和所有申请内存总量 相当的内存量,可用于管理;否则,这次申请后,会全部交给客户,下次客户申请(等量)内存时,很可能又要向系统申请。
注意:此时尚未求助于其他free list。

不过,在向OS申请前,要先把内存池的残余空间(不满足1个大小为n的区块,肯定 < 128bytes),加入某个合适的free list。

为什么要把内存池残余空间加入free list?
因为内存池只通过一对指针(start_free, end_free)来管理一块线性空间,向OS申请新内存后,无法再维护原来的内存空间,因此需要将原来空间的控制权交出去。

3.2)向OS申请内存,如果成功,直接更新内存池边界等信息,然后重新根据客户请求分配空间。

3.3)向OS申请内存,如果OS的heap空间不够,可能出现异常(malloc()返回空)。此时,需要进行异常处理。
A)先尝试在比size大的free list遍历查找,是否有可用而且足够大的区块。如果有,就直接取出该free list的第一个可用区块,交给内存池管理(此时内存池已经为空了),然后重新根据客户请求分配空间。因为找到的新区块 > 请求对象大小size,因此,至少能满足1个对象需求。

B)如果找遍所有free list,都没拿找到更足够大且可用的区块时,也就是说,到处找不到可用的内存,就调用一级配置器的allocate(),借助其out-of-memory机制:不断向申请内存、调用客户注册异常处理例程,或者直接抛出异常并终止程序。

内存池的chunk_alloc()流程:

chunk_alloc()源码:

// 假设size已经适当上调至8的倍数
// 注意参数nobjs是pass by reference
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; // 内存池剩余空间

       if (bytes_left >= total_bytes) {
              // 内存池剩余空间完全满足需求量, 从内存池直接分配所需量 start_free ~ start_free + total_bytes
              result = start_free;
              start_free += total_bytes; // 从内存池取出内存后, 移动内存池起始位置
              return (result);
       }
       else if (bytes_left >= size) {
              // 内存池剩余空间不能完全满足需求量, 但足够供应一个(含)以上的区块
              nobjs = bytes_left / size;  // 先分配能满足的块数
              total_bytes = size * nobjs; // 从内存池实际能分配的总量
              result = start_free;
              start_free += total_bytes;
              return (result);
       }
       else {
              // 内存池剩余空间连一个区块的大小都无法提供, 就需要向OS重新申请(malloc)内存
              // 默认申请 2倍所需量, heap_size 用来调整申请的内存量.
              // 注意: 为内存池申请空间, 分配空间时, 需要确保对齐(8byte对齐)
              size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); // >> 4 <=> /16

              // 先试着让内存池的残余零头还有利用价值, 因为不够申请的一个区块大小(size),
              // 因此内存池剩余空间肯定 < 128bytes, 可以加入某个区块
              if (bytes_left > 0) {
                     // 内存池还有一些零头, 先分配给恰当的free list, 以备其他客户向free list申请空间
                     // 首先寻找适当的free list
                     obj* volatile *my_free_list = free_list +  FREELIST_INDEX(bytes_left);

                     // 将内存池残余空间插入到free list槽位对应链表
                     // 调整free list, 将内存池中的残余空间编入
                     ((obj*)start_free)->free_list_link = *my_free_list;
                     *my_free_list = (obj*)start_free;
              }

              // 向OS heap申请新空间, 用来补充内存池. 此时内存池已经为空, 残余空间已经交给free list.
              start_free = (char*)malloc(bytes_to_get);
              if (0 == start_free) { // OS heap空间不足, malloc()失败后异常处理
                     int i;
                     obj* volatile * my_free_list, *p;

                     // 试着检查我们手上拥有的东西, 这不会造成伤害. 我们不打算尝试配置较小的区块,
                     // 因为那在多进程(multi-process)机器上容易导致灾难
                     // 以下搜寻适当的free list
                     // 所谓适当是指"尚有未用区块, 且区块够大"之free list
                     for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                           my_free_list = free_list + FREELIST_INDEX(i);
                           p = *my_free_list;

                           if (0 != p) { // free list内尚有未用区块
                                  // 调整free list以释放出未用区块
                                  *my_free_list = p->free_list_link;
                                  start_free = (char*)p;
                                  end_free = start_free + i;
                                         
                                  // 此时内存池已经有足够大区块. 递归调用自己, 为了修正nobjs
                                  return (chunk_alloc(size, nobjs));
                                  // 注意, 内存池任何残余零头终将被编入适当的free-list中备用
                           }
                     }

                     end_free = 0; // 如果出现意外(到处都没内存可用)

                     // 调用第一级配置器, 看看out-of-memory机制是否能尽点力
                     start_free = (char*)malloc_alloc::allocate(bytes_to_get);
                     // 这会导致抛出异常(exception), 或内存不足的情况获得改善
              }

              heap_size += bytes_to_get;            // 向OS成功申请到内存, 就扩大heap size
              end_free = start_free + bytes_to_get; // 更新内存池end_free边界

              // 此时内存池有足够空间, 递归调用自己, 为了修正nobjs
              return (chunk_alloc(size, nobjs));
       }
}
这篇关于SGI STL源码 空间配置器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!