阿龙咖啡 /

STL 源代码分析笔记 (2)

空间配置器

空间配置器 (allocator) 是构造各类 STL 容器的基本工具,它提供了寻址、配置/释放与对象构造/析构的基本策略。在 SGI STL 中通过内部头文件 stl_alloc.h 实现主要功能,并借由头文件 alloc.h 引出以供用户使用。

空间配置器的标准接口

这里是笔者从 stl_alloc.h 头文件中提取的 SGI STL 提供的与标准兼容的配置器接口,部分代码如下。

template <class _Tp>
class allocator {
  typedef alloc _Alloc;          // The underlying allocator.
public:
  typedef size_t     size_type;
  typedef ptrdiff_t  difference_type;
  typedef _Tp*       pointer;
  typedef const _Tp* const_pointer;
  typedef _Tp&       reference;
  typedef const _Tp& const_reference;
  typedef _Tp        value_type;

  template <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };

  allocator() __STL_NOTHROW {}
  allocator(const allocator&) __STL_NOTHROW {}
  template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {}
  ~allocator() __STL_NOTHROW {}

  pointer address(reference __x) const { return &__x; }
  const_pointer address(const_reference __x) const { return &__x; }

  // __n is permitted to be 0.  The C++ standard says nothing about what
  // the return value is when __n == 0.
  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) 
                    : 0;
  }

  // __p is not permitted to be a null pointer.
  void deallocate(pointer __p, size_type __n)
    { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const __STL_NOTHROW 
    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

template<>
class allocator<void> {
public:
  typedef size_t      size_type;
  typedef ptrdiff_t   difference_type;
  typedef void*       pointer;
  typedef const void* const_pointer;
  typedef void        value_type;

  template <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };
};

其中 allocator 类中包含一个指向名为 alloc 接口的类型别名 _Alloc,并且在接口函数中最终使用它进行空间配置,其实这个就是封装了 SGI STL 的底层实现的配置器接口,它通过名为 __USE_MALLOC 的宏决定使用一级配置器还是二级配置器 (见后文),为了给客户程序隐藏底层实现,它对客户程序提供一个标准的接口,才有了 allocator 这个类。

上述代码除了 allocator 类模板的定义之外,后半部分有一个对模板 void 类型参数进行全特化的定义,通过这种方式将它无效化,这是似乎是为了规避 void 类型对配置器行为产生影响的问题,譬如考虑一下 sizeof (void) 的值 (编译器相关),这一点很显然。

关于 __USE_MALLOC 宏的作用,代码中已经十分明显,为了方便观察,我省略了其余的代码内容,并将它们排版在一起。

#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;  // 令 alloc 为一级配置器
#else
typedef __default_alloc_template
<__NODE_ALLOCATOR_THREADS, 0> alloc;  // 令 alloc 为二级配置器
#endif

max_size 函数分析

此函数返回配置器理论上所支持的最大配置对应类型对象的数量值,譬如对于 allocate(n, 0) 而言,当 n <= max_size() 时,配置器才可能调用成功。

此处的 “调用成功” 指的是理论情况下,因此也有可能在实际中发生其他使之调用失败的情形。

在此处 (包括大多数其他 STL 实现),max_size 函数只是简单地返回 size_type的最大值除以 value_type 数据类型大小的值,如下所示。

/* stl_alloc.h : 623 */
size_type max_size() const __STL_NOTHROW 
    { return size_t(-1) / sizeof(_Tp); }

或者,这样等价的写法:

size_type max_size() const __STL_NOTHROW 
    { return numeric_limits<size_t>.max() / sizeof(value_type); }

construct 函数分析

此函数只是对 new 操作符简单地封装了一遍,具体实现十分简单,如下所示。

/* stl_alloc.h : 626 */
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }

其中,new(__p) _Tp(__val) 表示在指针 __p 所在的内存位置,调用类型 _Tp 的拷贝构造函数,这样将 __val 对象复制到 __p 所在的位置,从而完成对指针 __p 指向的对象的构造。

destroy 函数分析

此函数只是对析构函数简单地封装了一遍,此处不再赘述,如下所示。

/* stl_alloc.h : 626 */
void destroy(pointer __p) { __p->~_Tp(); }

此处需要注意的是 construct 函数与 destroy 函数都只是单纯地负责构造和析构,而不是配置内存和回收内存。construct 被调用时,指针 __p 是已指向被配置好的内存空间;同样地,destroy 被调用也并不负责 __p 所指向空间的释放操作。

具有次配置力 (sub-allocation) 的空间配置器

所谓次配置力,有一种解释为“次层配置”的能力,即预先从宏观上分配一整块空间,然后微观上划分为数个小型区块,并且通过内存池的方式进行配置与管理。
通过上文的定义,我们得知 (至少是字面意思上) 第一级配置器以底层只是简单地转去调用 malloc/free 函数完成空间配置与回收,通常这并不能带来分配效率的提升,尤其是当客户程序分配很多零碎的小区块空间时,这时可能还会产生内存碎片,并且对于系统而言,维护这些小区块也需要额外的开销 (比如用于记录空间大小的 cookie),造成效率下降。
SGI 提供了具有次配置力的空间配置器,即第二级配置器,被定义为 __default_alloc_template 类模板 (其实它的两个类型参数均未被使用),其主体代码如下。

template <bool threads, int inst>
class __default_alloc_template {

private:
  // Really we should use static const int x = N
  // instead of enum { x = N }, but few compilers accept the former.
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
    enum {_ALIGN = 8};
    enum {_MAX_BYTES = 128};
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
# endif
  static size_t
  _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

__PRIVATE:
  union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];    /* The client sees this.        */
  };
private:
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
    static _Obj* __STL_VOLATILE _S_free_list[]; 
        // Specifying a size results in duplicate def for 4.1
# else
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
# endif
  static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }

  // Returns an object of size __n, and optionally adds to size __n free list.
  static void* _S_refill(size_t __n);
  // Allocates a chunk for nobjs of size size.  nobjs may be reduced
  // if it is inconvenient to allocate the requested number.
  static char* _S_chunk_alloc(size_t __size, int& __nobjs);

  // Chunk allocation state.
  static char* _S_start_free;
  static char* _S_end_free;
  static size_t _S_heap_size;

# ifdef __STL_THREADS
    static _STL_mutex_lock _S_node_allocator_lock;
# endif

    // It would be nice to use _STL_auto_lock here.  But we
    // don't need the NULL check.  And we do need a test whether
    // threads have actually been started.
    class _Lock;
    friend class _Lock;
    class _Lock {
        public:
            _Lock() { __NODE_ALLOCATOR_LOCK; }
            ~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
    };

public:

  /* __n must be > 0      */
  static void* allocate(size_t __n)
  {
    void* __ret = 0;

    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      // Acquire the lock here with a constructor call.
      // This ensures that it is released in exit or during stack
      // unwinding.
#     ifndef _NOTHREADS
      /*REFERENCED*/
      _Lock __lock_instance;
#     endif
      _Obj* __RESTRICT __result = *__my_free_list;
      if (__result == 0)
        __ret = _S_refill(_S_round_up(__n));
      else {
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }

    return __ret;
  };

  /* __p may not be 0 */
  static void deallocate(void* __p, size_t __n)
  {
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
      _Obj* __STL_VOLATILE*  __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __q = (_Obj*)__p;

      // acquire lock
#       ifndef _NOTHREADS
      /*REFERENCED*/
      _Lock __lock_instance;
#       endif /* _NOTHREADS */
      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;
      // lock is released here
    }
  }

  static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);

};

第一级配置器

刚刚在上文我们提到了第一级配置器只是简单地转去调用 malloc/free 来配置空间。除此之外,对于第一级配置器而言,值得注意的是它还提供了 malloc-handler 的机制。所谓 malloc-handler,简单地说就是当 malloc 出现异常 (比如内存不足) 之时,程序调用它进行一些修正处理 (主要是使得 malloc 函数可用) 的例程。

在第一级配置器中,采用函数指针的方式来放置 malloc-handler,并且提供了 __set_malloc_handler 函数以供客户程序设置自定义的 malloc-handler,当内存配置异常时将不停地尝试调用 malloc-handler 以及 malloc 函数,企图获取空间、并且直到获取到空间为止;

若未提供 malloc-handler 则将抛出异常或者中止程序 (取决于__THROW_BAD_ALLOC 宏)。第一级配置器的主体代码与 malloc-handler 有关的注释说明均如下所示。

template <int __inst>
class __malloc_alloc_template {

private:

  static void* _S_oom_malloc(size_t);
  static void* _S_oom_realloc(void*, size_t);

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
  static void (* __malloc_alloc_oom_handler)();     /* malloc-handler 处理例程 */
#endif

public:

  static void* allocate(size_t __n)
  {
    void* __result = malloc(__n);
    if (0 == __result) __result = _S_oom_malloc(__n); /* 若 malloc 不成功则转而调用 _S_oom_malloc 函数 (其中包含 malloc-handler 例程的调用) */
    return __result;
  }

  static void deallocate(void* __p, size_t /* __n */)
  {
    free(__p);
  }

  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); /* 若 realloc 不成功则转而调用 _S_oom_realloc 函数 (其中包含 malloc-handler 例程的调用) */
    return __result;
  }

  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

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;   /* 默认不启用 malloc-handler */
#endif

template <int __inst>
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;     /* 获取 malloc-handler */
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }  /* 若不可用则直接 “抛出异常” */
        (*__my_malloc_handler)();       /* 尝试调用 malloc-handler */
        __result = malloc(__n);         /* 尝试调用 malloc */
        if (__result) return(__result); /* 若取得空间则返回,否则不断尝试 */
    }
}

template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;     /* 获取 malloc-handler */
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }  /* 若不可用则直接 “抛出异常” */
        (*__my_malloc_handler)();       /* 尝试调用 malloc-handler */
        __result = realloc(__p, __n);   /* 尝试调用 realloc */
        if (__result) return(__result); /* 若取得空间则返回,否则不断尝试 */
    }
}

第二级配置器

实际上,第二级配置器采用配置多种大小级别的区块,多样化地、弹性地管理内存。比如在第二级配置器的代码中有以下枚举定义:

enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

我们分别围绕这三个枚举定义来解释第二级配置器的主要原理。

字节对齐的实现

_ALIGN 表示字节对齐的数乘单位,第二级配置器其实是采用向上对齐的策略,譬如客户程序要求 29 字节的空间,配置器则会提供一块大于 29 字节、且能被 8 整除的空间,此处即一块 32 字节的空间。向上对齐的功能是由名为 _S_round_up 的成员函数提供,代码十分简洁,如下。

/* stl_alloc.h : 299 */
static size_t _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

该函数会将字节数向上对齐并返回,其中使用了一些小技巧提升计算效率,这个计算方法不难推导出来。

一大块空间

这种对不同大小级别的空间进行区分配置的方式最多到 _MAX_BYTES 停止,如果客户程序要求一块大于 _MAX_BYTES 的空间,那么根据 SGI STL 的实现,程序会认为此空间足够大,对于第二级配置器而言,这种算法已经失去提升效率的意义,因此,程序将简单地转而调用第一级配置器,即采用单纯的 malloc/free 方式配置空间。相关代码片段,分别处于 allocate 函数与 deallocate 函数之中,譬如以下代码 (allocate 函数)。

/* stl_alloc.h : 350 */
void* __ret = 0;

if (__n > (size_t) _MAX_BYTES) {
  __ret = malloc_alloc::allocate(__n); // 转而调用第一级配置器
}
else {
    /* ... 省略代码 ... */
}

大小级别与自由链表 (free-list)

_NFREELISTS 表示自由链表 (free-list) 的个数 (_MAX_BYTES / _ALIGN),所谓自由链表即是配置各个大小级别区块所采用的一种数据结构 (下文会说明),我们现在只需明白这代表了不同大小级别区块的个数,譬如区块以 8 字节对齐,最大字节数 128 字节,那么就有 128 / 8 = 16 个大小级别,分别是 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 字节大小级别的区块。

自由链表的节点结构在类中被定义成如下的联合体 (union)。可以看出,它使用了一种很巧妙的方式存储指向区块空间的指针。对于第二级配置器而言,客户程序每次请求相同大小的空间,都将从对应的大小级别的自由链表中取出;同样地,若客户程序归还这块空间,配置器就将其放回至对应大小级别的自由链表中。

/* stl_alloc.h : 304 */
union _Obj {
 union _Obj* _M_free_list_link;
 char _M_client_data[1];    /* The client sees this.        */
};

如上所示,free-list 节点利用了 union 的特性,既可以表示 free-list 的节点 (_M_free_list_link);同样也可以表示区块 (此处的 char _M_client_data[1]实际上即等价于char * const _M_client_data)。

配置器维护了 _NFREELISTS 个自由链表 (目前是 16 个),并且定义了一个工具函数来根据用户想要分配的字节数、即根据大小级别,决定使用哪一个自由链表。函数 _S_freelist_index 将根据输入字节数,返回自由链表对应的下标,譬如对于 29 字节,它将返回 3。其代码如下。

/* stl_alloc.h : 315 */
static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}

allocate 函数分析

接下来,我们通过阅读一段 allocate 成员函数中的代码来分析一下第二级配置器是如何使用自由链表完成空间配置的。

这段代码即上文中配置器对空间大小进行判断的,当配置空间大小不超过 _MAX_BYTES 的条件分支。

/* stl_alloc.h : 356 */
_Obj* __STL_VOLATILE* __my_free_list
    = _S_free_list + _S_freelist_index(__n); /* 选择对应大小级别的 free-list */
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
#ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
#endif
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0)
  __ret = _S_refill(_S_round_up(__n)); /* 对应大小级别的 free-list 为空,则填充,并且此函数直接将首个可用区块返回,下文会说明 */
else {
  *__my_free_list = __result -> _M_free_list_link; /* 因为将取出首个区块,所以应该将当前的指针调整,指向到下一个区块 */
  __ret = __result;  /* 将取出的首个区块返回 */
}

__my_free_list 即对应大小级别区块的自由链表的地址 (二级指针),通过 _S_free_list基址加上 _S_freelist_index(__n) 偏移下标量得到。

接下来,__result 即对应的自由链表 (一级指针),当它为 0 (即链表为 NULL) 时,即对应的大小级别区块还没有被配置过,这是第一次,所以调用 _S_refill(_S_round_up(__n)) 进行配置,得到空间地址并返回,此处的原理下文会提到。

如果 __result 不为 0,那么就将它作为空间地址返回。并且将 __result 指向的下一个节点覆盖当前_S_free_list 中对应的链表,这又将使得它作为对应大小区块的下一次配置空间的地址。

细品之下,其实这里有点 p = p->next 的意味,但是并不完全是。这里不妨可多花些时间,逐步分析,使自己理解透彻。

_S_refill 函数分析

上文我们了解到,当区块不足时,allocate 函数将调用 _S_refill 函数进行补充。它接受一个空间大小 __n 作为参数,通常是已经被 _S_round_up 函数对齐了的大小数值。函数的代码如下。

/* stl_alloc.h : 492 */
/* Returns an object of size __n, and optionally adds to size __n free list.*/
/* We assume that __n is properly aligned.                                */
/* We hold the allocation lock.                                         */
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs); /* 尝试获取 __nobjs 个空间大小为 __n 的区块,并将取得小于等于 __nobjs 个区块 */
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    if (1 == __nobjs) return(__chunk); /* 只能取得一个区块,直接将其返回 */
    __my_free_list = _S_free_list + _S_freelist_index(__n); /* 选择对应大小级别的 free-list */

    /* Build free list in chunk */
      __result = (_Obj*)__chunk;
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);  /* 第 2 个区块 */
      for (__i = 1; ; __i++) {
        __current_obj = __next_obj;  /* 迭代操作 */
        __next_obj = (_Obj*)((char*)__next_obj + __n);  /* 迭代操作 */
        if (__nobjs - 1 == __i) { /* 最后一个区块,末尾补 0 */
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj; /* 串起来 */
        }
      }
    return(__result);
}

其中变量 __nobjs 表示期望获取到的区块数量,自然是在有限的范围内越大越好,这里默认是 20 个。__n__nobjs 将一并传递给 _S_chunk_alloc 函数以从内存池 (下文将说明该函数) 中获取区块,现在只用知道 _S_chunk_alloc 函数将从某处取得区块就行了。另外,此函数还可能改变 __nobjs 的值,因为它有可能无法完全获取到这么多的区块,它只是最大限度地获取区块,并将其数量覆盖到 __nobjs 返回。

取得的区块将被 __chunk 指针指向,接下来就是判定 __nobjs 的值,如果只分配到了 1 个区块,那么就简单地将 __chunk 指针返回。如果大于 1 个区块,就将大于 1 个区块的部分,一个接一个地 “串” 起来,构造一个自由链表并填充对应大小级别的 free-list,直到最后一个区块 (然后尾节点以 0 结尾)。然后把第 1 个区块作为自由链表的头部返回。

代码文件 stl_alloc.h 中 511 ~ 512 行附近,头节点并没有对它的下一个节点 (即第 2 个节点) 进行链接 (赋值),这是因为这个区块将直接被调用者,即 allocate 函数取走,并直接被 allocate 函数返回给客户程序。所以,为了提升效率,这里直接将它返回,不做从它到第二个节点的链接操作。

_S_chunk_alloc 函数分析

为了方便说明,我们首先从底层开始分析,比如关于内存池 (memory pool) 在第二级配置器中的具体原理。主要的实现代码包含在 _S_chunk_alloc函数里面,相关代码如下。

/* stl_alloc.h : 427 */
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
                                                            int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs;
    size_t __bytes_left = _S_end_free - _S_start_free;

    if (__bytes_left >= __total_bytes) {  /* 第 1 种情况 */
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else if (__bytes_left >= __size) {  /* 第 2 种情况 */
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {  /* 第 3 种情况 */
        size_t __bytes_to_get = 
      2 * __total_bytes + _S_round_up(_S_heap_size >> 4); /* 新大小,2倍需求量外加一个随着分配次数增加而增大的附加量 */
        // Try to make use of the left-over piece.
        if (__bytes_left > 0) { /* 虽然都无法供应一个区块,当还有残渣可以使用时 */
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);
            /* 将该区块加入对应大小级别的自由链表中,换一种方式,物尽其用 */
            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
        _S_start_free = (char*)malloc(__bytes_to_get); /* 直接调用 malloc 配置内存 */
        if (0 == _S_start_free) {
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
        _Obj* __p;
            // Try to make do with what we have.  That can't
            // hurt.  We do not try smaller requests, since that tends
            // to result in disaster on multi-process machines.
            /* 尝试寻找一个有可用区块的、足够大的 free-list */
            for (__i = __size;
                 __i <= (size_t) _MAX_BYTES;
                 __i += (size_t) _ALIGN) {
                __my_free_list = _S_free_list + _S_freelist_index(__i);
                __p = *__my_free_list;
                if (0 != __p) { /* 找到,就将其取走,作为内存池的新空间 */
                    *__my_free_list = __p -> _M_free_list_link;
                    _S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;
                    return(_S_chunk_alloc(__size, __nobjs)); /* 调用自身修正 __nobjs 值,接下来一般会成功分配区块 */
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
            /* 如果无论如何都没有剩余空间了,就转去调用第一级配置器的 allocate 函数,试图利用第一级配置器的 malloc-handler 机制以解决之前的 malloc 问题 */
        _S_end_free = 0;    // In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
            /* 调用这个要么抛出异常,要么配置问题被解决 */
        }
        /* 通过上述某种手段,成功获得新空间,设置/调整各变量值 */
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs)); /* 调用自身修正 __nobjs 值,接下来一般会成功分配区块 */
    }
}

在二级配置器中,内存池是使用一大块连续空间实现的,类的内部维护了一对指针,_S_start_free_S_end_free ,分别指示了内存池的起始位置与结束位置,当调用者从内存池抽取空间时,_S_start_free 将增长,内存池剩余的大小 (__bytes_left = _S_end_free - _S_start_free ) 则会变小。

因此,对于单个区块大小 (__size) * 区块数量 (__nobjs) 的连续空间,尝试从内存池中抽取时,将出现包含 3 种不同的情况:

1. 足够供应:所有区块

2. 足够供应:一个 (含) 以上的区块

3. 无法供应任何区块

对于第 1 种情况的处理很简单,直接将 _S_start_free 指针作为结果返回,并将其直接地向后偏移 __total_bytes 字节大小 ( __size * __nobjs),也就是将剩余空间完整地、大胆地分配给调用者。

配置器出于对内存尽可能地利用,减少内存空间的浪费,减少申请 malloc 的次数,所以需要考虑内存即便在不可完全利用的情况下,能否只是满足调用者的一部分需求。如果可以就尽可能使用剩余空间满足其一部分需求,之后再对超出的需求部分做出处理。

所以,对于第 2 种情况而言,之前我们在分析 _S_refill 函数时提到过,“ 此函数还可能改变 __nobjs 的值,因为它有可能无法完全获取到这么多的区块,它只是最大限度地获取区块,并将其数量覆盖到 __nobjs 返回 ”。这刚好就是配置器对于第 2 种情况所做出的策略,它重新计算并更新 __nobjs 的值,使之记录了内存池中最多可以分配的区块数,接着分配了这些区块:这与第 1 种情况类似,它将 _S_start_free 指针作为返回,并将其直接地向后偏移 __total_bytes 字节大小 ( __size * __nobjs)。

第 3 种情况相对比较复杂,我们逐步分析。

内存池中可能仍有内存剩余,但是不足以完整地供应一个区块,对于这种情况,首先我们需要将它通过另外一种方式利用起来,并且是要将它移走,这样才能在现在的位置重新配置足够大的空间。这里的做法是:转而将内存池中剩余的空间一并作为更小的区块,将其抽出、附加到对应大小级别的 free-list 上。这样的话,这些剩余空间就可以通过另外一种形式继续为配置器效力,达到物尽其用之目的。

无论如何分配,剩余空间必是按照 _ALIGN 的倍数对齐的,所以无需考虑对齐情况

无论是否有内存剩余,终究需要重新向系统申请足够大的空间,只不过如果有剩余空间,就需要以上处理过程,否则就可以直接向系统申请空间而无需做处理。

申请新空间的大小,是调用者需求大小的 2 倍加上一个随着分配次数增加而增大的附加量。因为 _S_heap_size 记录了配置器内存池中,向系统总共申请的空间大小,随着程序的运行,它必然是随着分配次数增加而增大的量。

/* stl_alloc.h : 447 */
size_t __bytes_to_get = 
      2 * __total_bytes + _S_round_up(_S_heap_size >> 4);

接着就是调用 malloc 函数以取得空间。如果 malloc 函数失败,如你所见的那样,配置器将按照区块大小级别,从调用者需求的区块大小开始、从小到大地遍历所有的 free-list,通过这样做来寻找一个有可用区块的、足够大的 free-list。如果有,就将其从 free-list 中取走,并将其作为内存池的新空间;最后,调函数自身以修正 __nobjs 的值 (这样做一般会成功给调用者返回区块)。

如果无论何处都已经没有空间可用了,那么配置器将作最后一搏,转而调用第一级配置器的 allocate 函数。因为我们之前讲过第一级配置器的 malloc-handler 特性,第一级配置器将尝试配置内存,如果出错,在没有 malloc-handler 的情况下将直接抛出异常;否则,就将调用 malloc-handler 处理例程来尝试修复内存不足的情况,之后试图再调用 malloc 函数以取得空间,就这样一直循环往复。直到 malloc 能够获取到空间或者其他情况 (譬如 malloc-handler 也抛出异常)。

总之,第二级配置器将不断地尝试任何可能的办法来解决空间不足的情形。但是也不可避免的可能会遇到完全无法修正的情形,这样抛出异常就是当所有尝试都失效后的最好的解决方案。

当通过上述途径 (直接调用 malloc、寻找可用的 free-list 以取走区块、调用第一级配置器) 获取到了空间之后,最终就对 _S_start_free_S_end_free_S_heap_size 做出调整,最终调用函数自身以修正 __nobjs 的值。

其实只要发生第 3 种情况,递归调用自身以求修正 __nobjs 的值都是处理完一切情形必须做的工作,毕竟可以分配给调用者的区块数量会在情形修正后而发生改变。

deallocate 函数分析

以下就是 deallocate 函数的全貌,与 allocate 函数类似,当释放空间大小超过 _MAX_BYTES 之时,将转而调用第一级配置器的 deallocate 函数;否则,就将其归还、插入到对应大小级别的 free-list 中,与 allocate 函数的作用相反。

/* stl_alloc.h : 377 */
/* __p may not be 0 */
static void deallocate(void* __p, size_t __n)
{
  if (__n > (size_t) _MAX_BYTES)
    malloc_alloc::deallocate(__p, __n);
  else {
    _Obj* __STL_VOLATILE*  __my_free_list
        = _S_free_list + _S_freelist_index(__n);
    _Obj* __q = (_Obj*)__p;

    // acquire lock
#     ifndef _NOTHREADS
    /*REFERENCED*/
    _Lock __lock_instance;
#     endif /* _NOTHREADS */
    __q -> _M_free_list_link = *__my_free_list;
    *__my_free_list = __q;
    // lock is released here
  }
}

简单配置器接口

另外,我们可以观察到,头文件 stl_alloc.h 中,定义了 simple_alloc 类模板,它接收两个模板参数,第一个是每个单元的数据类型,这里不做赘述;第二个是底层使用的配置器类型 (第一级配置器或者第二级配置器,根据 __USE_MALLOC 宏决定)。乍一看,这与我们文章开头讲过的 allocator 类模板相似。但是,simple_alloc 类模板可以直接通过模板参数指定底层使用的配置器类型,并且它的接口十分简洁 (顾名思义),只提供了两组 (共 4 个) 成员函数:allocatedeallocate

simple_alloc 类模板是直接被 SGI STL 中的容器直接使用的,笔者认为这种编程手法是为了实现接口隔离原则 (Interface Segregation Principle, ISP),对于容器而言,供它调用的配置器的接口最好保持简单 (只保留 allocatedeallocate),所以就用 simple_alloc 的方式定义一个简单的中间层,将配置器的具体实现、多余的接口细节与容器的业务代码隔离开。

未初始化空间 (uninitialized) 处理函数

SGI STL 在内部头文件 <stl_uninitialized> 中实现了一些全局函数:uninitialized_copyuninitialized_filluninitialized_fill_n (最终通过 <memory> 引出这些函数) 等。这些函数,用于直接操作未初始化 (uninitialized) 空间,这些函数是实现容器的最重要的基本工具。下文中我们会逐个地了解它们。

一般分析

我们先分析 3 个核心的函数 uninitialized_copyuninitialized_filluninitialized_fill_n,了解了它们的作用之后,我们就可以深入地分析其他函数以及底层实现的一些技巧。

uninitialized_copy 函数

声明式如下,其作用是将迭代器 __first__last 所组成的闭区间 [__first, __last) 的所有对象,通过拷贝并重新构造 (通过调用 construct 函数) 到以迭代器 __result 起始的内存空间中。该函数返回指示目标的迭代器在经过逐次拷贝,递增移动后的最终位置 (一般是 __result + (__last - __first))。

template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last,
                   _ForwardIter __result);

uninitialized_copy 函数的最终实现代码如下 (经过简化处理)。

_ForwardIter __cur = __result;
try {
  for ( ; __first != __last; ++__first, ++__cur)
    _Construct(&*__cur, *__first);  /* 调用全局的 _Construct 函数,此函数与配置器的 construct 成员函数功能相同 */
} catch (...) { /* 若构造发生异常 */
    _Destroy(__result, __cur);  /* 调用全局的 _Destroy 函数,这个函数的功能是对已经构造完成的区间 [__result, __cur) 中的每一个对象都逐一调用 destroy 函数进行析构 */
    throw;
}
return __cur;

如你所见,当构造期间发生异常之时,函数将会把之前已经构造的所有对象全部析构,即区间内的对象要么全部成功地构造,要么失败:一个都不构造,这被称为 “commit or rollback” 策略。之后继续向上层代码抛出异常。

需要注意的是 uninitialized_copy 函数只是单纯地将源位置的的对象,成区间地拷贝构造到目标位置。所以在这之前需要一块已经配置好的目标空间,此函数并不负责内存的配置。

uninitialized_fill 函数

声明式如下,其作用是将源对象 x 通过调用 construct 函数拷贝并重新构造到迭代器 __first__last 所组成的闭区间 [__first, __last) 的内存空间中。可以这么理解,其功能也就是复制很多份 x[__first, __last) 中。

template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,
                               _ForwardIter __last, 
                               const _Tp& __x);

uninitialized_copy 函数一样,uninitialized_fill 函数同样具备 “commit or rollback” 策略,此处不再赘述。以下是 uninitialized_fill 函数的大致代码如下。

_ForwardIter __cur = __first;
try {
  for ( ; __cur != __last; ++__cur)
    _Construct(&*__cur, __x);  /* 调用全局的 _Construct 函数,此函数与配置器的 construct 成员函数功能相同 */
} catch (...) { /* 若构造发生异常 */
    _Destroy(__first, __cur);  /* 调用全局的 _Destroy 函数,这个函数的功能是对已经构造完成的区间 [__first, __cur) 中的每一个对象都逐一调用 destroy 函数进行析构 */
    throw;
}

uninitialized_fill_n 函数

声明式如下,其作用是将源对象 x 通过调用 construct 函数拷贝并重新构造到迭代器 __first__first + n 所组成的闭区间 [__first, __first + __n) 的内存空间中。可以这么理解,其功能也就是复制 __nx 到以 __first 起始的内存空间中。该函数返回指示目标的迭代器 __first 在经过逐次拷贝,递增移动后的最终位置 (一般为 __first + __n)。

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter 
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
  return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}

与上文中介绍的两个函数一样,uninitialized_fill_n 函数同样具备 “commit or rollback” 策略,此处不再赘述。以下是 uninitialized_fill_n 函数的大致代码如下。

_ForwardIter __cur = __first;
try {
    for ( ; __n > 0; --__n, ++__cur)
      _Construct(&*__cur, __x);  /* 调用全局的 _Construct 函数,此函数与配置器的 construct 成员函数功能相同 */
    return __cur;
} catch (...) {  /* 若构造发生异常 */
    _Destroy(__first, __cur);  /* 调用全局的 _Destroy 函数,这个函数的功能是对已经构造完成的区间 [__first, __cur) 中的每一个对象都逐一调用 destroy 函数进行析构 */
    throw;
}

深层分析

实际上,这 3 个函数的具体实现比上文所述更加复杂,上文中只是叙述了比较平凡的一种情况。我们现在来深入地分析这 3 个函数在各种不同情形下的具体实现。

POD (Plain Old Data) 类型

要理解下文中代码所使用的类型萃取技术,首先得理解 POD (Plain Old Data) 类型的意义。

实际上,POD 类型就是标量类型 (scalar types),比如 int, char, long, double, float, short 等,或者 C 中的纯 struct、enum。这些类型都有 trivial (平凡的) 的构造 (ctor)、析构 (dtor)、拷贝 (copy)、赋值 (assignment) 函数。换言之,作用在这些类型的构造、析构、拷贝和赋值函数,均具有可以被接受的默认参数,并且其构造行为也只是作用在内存数据之上的初始化,拷贝行为也是作用在内存数据上的直接拷贝。

uninitialized_copy 函数

通过阅读 stl_construct.h 头文件,不难看出 uninitialized_copy 函数会执行如下调用,最终实现其功能。相关代码如下。

/* stl_construct.h : 36 */
// uninitialized_copy

// Valid if copy construction is equivalent to assignment, and if the
//  destructor is trivial.
template <class _InputIter, class _ForwardIter>
inline _ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __true_type)
{
  return copy(__first, __last, __result);
}

template <class _InputIter, class _ForwardIter>
_ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __false_type)
{
  _ForwardIter __cur = __result;
  __STL_TRY {
    for ( ; __first != __last; ++__first, ++__cur)
      _Construct(&*__cur, *__first);
    return __cur;
  }
  __STL_UNWIND(_Destroy(__result, __cur));
}


template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result, _Tp*)
{
  typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
  return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}

template <class _InputIter, class _ForwardIter>
inline _ForwardIter
  uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result)
{
  return __uninitialized_copy(__first, __last, __result,
                              __VALUE_TYPE(__result));
}

inline char* uninitialized_copy(const char* __first, const char* __last,
                                char* __result) {
  memmove(__result, __first, __last - __first);
  return __result + (__last - __first);
}

inline wchar_t* 
uninitialized_copy(const wchar_t* __first, const wchar_t* __last,
                   wchar_t* __result)
{
  memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
  return __result + (__last - __first);
}

1、若迭代器为 const wchar_t * 型,则调用 const wchar_t * 特化版本的uninitialized_copy 函数,最终将调用 memmove 函数完成宽字符串常量的移动,调用结束。
若迭代器为 const char_t * 型,则调用 const char_t * 特化版本的uninitialized_copy 函数,最终将调用 memmove 函数完成字符串常量的移动,调用结束。
否则,调用泛化版本的 uninitialized_copy 函数。接下来转到第 2 步。

2、萃取并判断迭代器的类型,若为 POD (Plain Old Data) 类型就调用 __uninitialized_copy_aux 函数的特化版本 (最终执行 a 操作),否则调用其泛化版本 (最终执行 b 操作)。
a. 直接调用 STL 的 copy 函数,直接拷贝内存数据到目标内存区域,调用结束。
b. 将元素逐个调用 construct 函数,拷贝并重新构造到目标内存区域,调用结束。

调用层次关系图如下图所示。

QQ截图20201219181053.png

uninitialized_fill 函数

uninitialized_copy 函数类似,uninitialized_fill 函数同样会根据实际类型情况转而选择调用不同的底层代码。

/* stl_construct.h : 141 */
// Valid if copy construction is equivalent to assignment, and if the
// destructor is trivial.
template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, 
                         const _Tp& __x, __true_type)
{
  fill(__first, __last, __x);
}

template <class _ForwardIter, class _Tp>
void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, 
                         const _Tp& __x, __false_type)
{
  _ForwardIter __cur = __first;
  __STL_TRY {
    for ( ; __cur != __last; ++__cur)
      _Construct(&*__cur, __x);
  }
  __STL_UNWIND(_Destroy(__first, __cur));
}

template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, 
                                 _ForwardIter __last, const _Tp& __x, _Tp1*)
{
  typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
  __uninitialized_fill_aux(__first, __last, __x, _Is_POD());
                   
}

template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,
                               _ForwardIter __last, 
                               const _Tp& __x)
{
  __uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}

根据上述代码我们可以得知 uninitialized_fill 函数的调用规律。

1、萃取并判断迭代器的类型,若为 POD (Plain Old Data) 类型就调用 __uninitialized_fill_aux 函数的特化版本 (最终执行 a 操作),否则调用其泛化版本 (最终执行 b 操作)。
a. 直接调用 STL 的 fill 函数,直接复制多份__x 的原始内存数据到指定的区间 [__first, __last) 中,调用结束。
b. 将元素逐个调用 construct 函数,复制多份原始对象__x 并重新构造到目标内存区域 [__first, __last)中,调用结束。

调用层次关系图如下图所示。

QQ截图20201219195252.png

uninitialized_fill_n 函数

直接上代码吧。其实如果读者能看到此处,基本上也是对前两个函数的 “套路” 十分了解了。

/* stl_construct.h : 181 */
// Valid if copy construction is equivalent to assignment, and if the
//  destructor is trivial.
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
                           const _Tp& __x, __true_type)
{
  return fill_n(__first, __n, __x);
}

template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
                           const _Tp& __x, __false_type)
{
  _ForwardIter __cur = __first;
  __STL_TRY {
    for ( ; __n > 0; --__n, ++__cur)
      _Construct(&*__cur, __x);
    return __cur;
  }
  __STL_UNWIND(_Destroy(__first, __cur));
}

template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter 
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
  typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
  return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter 
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
  return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}

根据上述代码我们也可以得知 uninitialized_fill_n 函数的调用规律。

1、萃取并判断迭代器的类型,若为 POD (Plain Old Data) 类型就调用 __uninitialized_fill_n_aux 函数的特化版本 (最终执行 a 操作),否则调用其泛化版本 (最终执行 b 操作)。
a. 直接调用 STL 的 fill 函数,直接复制 __n__x 的内存数据到以目标位置起始的一段空间[__first, __first + __n) 中,调用结束。
b. 将元素逐个调用 construct 函数,复制 __n 份原始对象__x 并重新构造到目标位置起始的一段空间 [__first, __first + __n) 中,调用结束。

调用层次关系图如下图所示。

QQ截图20201219200247.png

留下一条评论

暂无评论