stl sgi 一级分配器 二级分配器 分配器

STL分配器

分配器

在VS中, 分配器如下:

template<class _Ty>
    class allocator
    {    // generic allocator for objects of class _Ty
public:
    static_assert(!is_const<_Ty>::value,
        "The C++ Standard forbids containers of const elements "
        "because allocator<const T> is ill-formed.");

    typedef void _Not_user_specialized;

    typedef _Ty value_type;

    typedef value_type *pointer;
    typedef const value_type *const_pointer;

    typedef value_type& reference;
    typedef const value_type& const_reference;

    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    typedef true_type propagate_on_container_move_assignment;
    typedef true_type is_always_equal;

    template<class _Other>
        struct rebind
        {    // convert this type to allocator<_Other>
        typedef allocator<_Other> other;
        };

    pointer address(reference _Val) const _NOEXCEPT
        {    // return address of mutable _Val
        return (_STD addressof(_Val));
        }

    const_pointer address(const_reference _Val) const _NOEXCEPT
        {    // return address of nonmutable _Val
        return (_STD addressof(_Val));
        }

    allocator() _THROW0()
        {    // construct default allocator (do nothing)
        }

    allocator(const allocator<_Ty>&) _THROW0()
        {    // construct by copying (do nothing)
        }

    template<class _Other>
        allocator(const allocator<_Other>&) _THROW0()
        {    // construct from a related allocator (do nothing)
        }

    template<class _Other>
        allocator<_Ty>& operator=(const allocator<_Other>&)
        {    // assign from a related allocator (do nothing)
        return (*this);
        }

    void deallocate(pointer _Ptr, size_type _Count)
        {    // deallocate object at _Ptr
        _Deallocate(_Ptr, _Count, sizeof (_Ty));
        }

    _DECLSPEC_ALLOCATOR pointer allocate(_CRT_GUARDOVERFLOW size_type _Count)
        {    // allocate array of _Count elements
        return (static_cast<pointer>(_Allocate(_Count, sizeof (_Ty))));
        }

    _DECLSPEC_ALLOCATOR pointer allocate(_CRT_GUARDOVERFLOW size_type _Count, const void *)
        {    // allocate array of _Count elements, ignore hint
        return (allocate(_Count));
        }

    template<class _Objty,
        class... _Types>
        void construct(_Objty *_Ptr, _Types&&... _Args)
        {    // construct _Objty(_Types...) at _Ptr
        ::new ((void *)_Ptr) _Objty(_STD forward<_Types>(_Args)...);
        }

    template<class _Uty>
        void destroy(_Uty *_Ptr)
        {    // destroy object at _Ptr
        _Ptr->~_Uty();
        }

    size_t max_size() const _NOEXCEPT
        {    // estimate maximum array size
        return ((size_t)(-1) / sizeof (_Ty));
        }
    };

        // CLASS allocator<void>
template<>
    class allocator<void>
    {    // generic allocator for type void
public:
    typedef void _Not_user_specialized;

    typedef void value_type;

    typedef void *pointer;
    typedef const void *const_pointer;

    template<class _Other>
        struct rebind
        {    // convert this type to an allocator<_Other>
        typedef allocator<_Other> other;
        };

    allocator() _THROW0()
        {    // construct default allocator (do nothing)
        }

    allocator(const allocator<void>&) _THROW0()
        {    // construct by copying (do nothing)
        }

    template<class _Other>
        allocator(const allocator<_Other>&) _THROW0()
        {    // construct from related allocator (do nothing)
        }

    template<class _Other>
        allocator<void>& operator=(const allocator<_Other>&)
        {    // assign from a related allocator (do nothing)
        return (*this);
        }
    };

分配器是一个模板类, 其中如下部分是STL要求的:

    typedef _Ty value_type;

    typedef value_type *pointer;
    typedef const value_type *const_pointer;

    typedef value_type& reference;
    typedef const value_type& const_reference;

    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

如果我们要自己实现一个分配器, 必须也有以上属性.

特点

在STL中, 我们一个对象获取内存空间以及调用构造函数都是分开的.
它将 new operator 分解成了 operator new 和 placement new 两步.

在SGI STL中,

• stl_alloc.h 进行内存的分配
• stl_construct.h 进行对象的构造和析构
• stl_uninitialized.h 对空间中的内存进行操作, 操作效率高

OOM处理

SGI STL中, 对OOM异常的处理如下:

#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

当我们在分配内存的时候, 很容易出现 没有可用内存 的问题, 就发生了 bad_alloc
在C++中, 如果发上了 bad_alloc, 在 <new> 头文件中, 会调用 __set_malloc_handler 设置一个回调函数来进行处理

实现如下:

  static void (* __set_malloc_handler(void (*__f)()))()
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
  }

其中,

• __set_malloc_handler 是一个 函数指针
• 它接受的参数也是 函数指针, 类型为 void (*__f)()
• 它的返回值也是一个函数指针, 类型为 void (* __old)()

以上说法第三条可能不是特别准确.

如果发生了 OOM, 则进行如下处理:

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;
        if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*__my_malloc_handler)();
        __result = malloc(__n);
        if (__result) return(__result);
    }
}

• 如果没有定义 __malloc_alloc_oom_handler 函数, 直接抛出异常
• 否则, 执行 __malloc_alloc_oom_handler
• 然后在尝试分配, 一直到成功.

分配器的两级

分配器共有两级.

• 如果超过128byte, 则由 __malloc_alloc_template 去分配.

  • 每次都会调用 malloc 方法

• 如果不超过, 则由 __default_alloc_template 进行分配, 其实就不会进行分配.

  • 其实它就是个内存池, 拥有128byte空间
  • 不超过, 要几个给几个.
  • 不会调用 malloc, 在已有的内存中给你使用.

二级分配器 __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
    // __STL_VOLATILE宏表示 是否可被外部所修改
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
# endif

  // 进行如下的计算
  // (n + 7) / 8 - 1
  // 如果我要分配 4, 结果为0 
  // 就返回 下标 0
  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;

    // 如果分配的大小 > 128byte, 则调用一级分配器
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      // 如果分配4byte, 则从 _S_free_list[0] 开始
      _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的指针
      _Obj* __RESTRICT __result = *__my_free_list;
      // 如果没有, 进行 _S_refill, 详细看下面
      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);

} ;

来看一看 _S_refill

/* 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;
    // _S_chunk_alloc 见下面
    char* __chunk = _S_chunk_alloc(__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);

    /* Build free list in chunk */
      __result = (_Obj*)__chunk;
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
      for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

来看看 _S_chunk_alloc

/* We allocate memory in large chunks in order to avoid fragmenting     */
/* the malloc heap too much.                                            */
/* We assume that size is properly aligned.                             */
/* We hold the allocation lock.                                         */
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) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else if (__bytes_left >= __size) {
    // 如果我未分配的内存 >= __size, 则进行最小分配
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
    // 空间不够, 进行递归分配
        // 首先内存对齐
        size_t __bytes_to_get = 
      2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        // 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);
        // 如果没有内存了
        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.
            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));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
        _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));
    }
}

这就是一个内存池的经典实现.

小技巧

我们无论malloc了多少, free的时候都能准确的free, 我们可以如下实现:

// Allocator adaptor to check size arguments for debugging.
// Reports errors using assert.  Checking can be disabled with
// NDEBUG, but it's far better to just use the underlying allocator
// instead when no checking is desired.
// There is some evidence that this can confuse Purify.
template <class _Alloc>
class debug_alloc {

private:

  enum {_S_extra = 8};  // Size of space used to store size.  Note
                        // that this must be large enough to preserve
                        // alignment.

public:

  static void* allocate(size_t __n)
  {
    char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
    *(size_t*)__result = __n;
    return __result + (int) _S_extra;
  }

  static void deallocate(void* __p, size_t __n)
  {
    char* __real_p = (char*)__p - (int) _S_extra;
    assert(*(size_t*)__real_p == __n);
    _Alloc::deallocate(__real_p, __n + (int) _S_extra);
  }

  static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
  {
    char* __real_p = (char*)__p - (int) _S_extra;
    assert(*(size_t*)__real_p == __old_sz);
    char* __result = (char*)
      _Alloc::reallocate(__real_p, __old_sz + (int) _S_extra,
                                   __new_sz + (int) _S_extra);
    *(size_t*)__result = __new_sz;
    return __result + (int) _S_extra;
  }

};

未完待续...

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-05 at 04:34 pm