第二章空间配置器(allocator)

预计阅读时间19 分钟 247 views

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 destructorgeneralized

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 destructorspecified

templace<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type){
    for(; first < last; ++first) destroy(&*first);
}

C++

元素类型有trivial destructorspecified

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抛出异常(操作失败)，则将所有成功产生的元素全部析构掉。

第二章空间配置器(allocator)

1. 空间配置器的标准接口

1.1 一般接口(generalized)

1.2 特殊化接口(specified)

1.3 设计一个简单的空间配置器

2. SGI空间配置器

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

2.2 SGI特殊的空间配置器 `std::alloc`

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

2.4 空间的配置与释放 `std::alloc`

2.5 第一级配置器 __ malloc_alloc_template 剖析

2.6 第二级配置器 __default_alloc_template 剖析

2.7 空间配置函数 `allocate()`

2.8 空间释放函数 `deallocate()`

2.9 重新填充`free lists`

2.10 内存池 `memory pool`

2.11 内存基本处理工具

uninitialized_copy()

uninitialized_fill

uninitialized_fill_n

Leave a Comment 取消回复

CONTENTS

第二章 空间配置器(allocator)

1. 空间配置器的标准接口

1.1 一般接口(generalized)

1.2 特殊化接口(specified)

1.3 设计一个简单的空间配置器

2. SGI空间配置器

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

2.2 SGI特殊的空间配置器 std::alloc

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

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

2.5 第一级配置器 __ malloc_alloc_template 剖析

2.6 第二级配置器 __default_alloc_template 剖析

2.7 空间配置函数 allocate()

2.8 空间释放函数 deallocate()

2.9 重新填充free lists

2.10 内存池 memory pool

2.11 内存基本处理工具

uninitialized_copy()﻿

uninitialized_fill﻿

uninitialized_fill_n﻿

Leave a Comment 取消回复