目錄

• 總覽
• 全局對象構(gòu)建析構(gòu)
• 全局區(qū)間對象fill/copy
• 雙頂層內(nèi)存緩沖器
• 示例
• reference

總覽

大體stg-stl分為alloctor, iter, adapter, container, algorithms, functions
原圖來自note/STL源碼剖析.md at master · arkingc/note · GitHub

• stl_construct.h 全局對象的構(gòu)建(ctor), 析構(gòu)(dector), 對其stl接口標(biāo)準(zhǔn)
• stl_uninitialized.h 全局對象的賦值, 初始化等, 這部分也是對其stl接口標(biāo)準(zhǔn)
• stl_alloc.h 全局雙頂層對象緩沖

全局對象構(gòu)建析構(gòu)(stl_construct.h)

這里函數(shù)_XXX(比如_Construct)都是stg內(nèi)置的函數(shù), 下面這種是對其stl標(biāo)準(zhǔn)接口

// --------------------------------------------------
// Old names from the HP STL.

template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value)

這里以construct為線看一下, 這里有兩個(gè)特點(diǎn):

1. 構(gòu)建對象一般是: [內(nèi)存分配] -> [構(gòu)造器], 這里使用placement new算子, 僅僅調(diào)用構(gòu)造器, 這樣object(s)的內(nèi)存和ctor就解耦了
2. 區(qū)分對待trival對象, 因?yàn)閠rival對象可以使用更加高效的構(gòu)建方式.
   簡單的結(jié)構(gòu)如下:

    construct(_T1* __p, const _T2& __value) 
      -> _Construct(_T1* __p, const _T2& __value) { new ((void*) __p) _T1(__value); }
    construct(_T1* __p) 
      -> void _Construct(_T1* __p) { new ((void*) __p) _T1(); }
    destroy(_ForwardIterator __first, _ForwardIterator __last) 
      -> _Destroy(_ForwardIterator __first, _ForwardIterator __last) 
        -> __destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*) 萃取當(dāng)前類型是否有析構(gòu)  
         有 -> __destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) for-each destroy(&*__first); 
          無 -> 啥都不干, 這一步只是為了析構(gòu), trival無需特殊析構(gòu)

在看過上面例子夠, 這里引申兩點(diǎn):

1. c++本身是靜態(tài)語言, 不能運(yùn)行時(shí)獲取object的meta info, 所以萃取其實(shí)是一個(gè)編寫上的契約, 比如當(dāng)前以迭代器(iter)方式構(gòu)建或者刪除時(shí), 從迭代器可以獲取value類型, 從value類型就可以知道是否是trivial類型, 假如自定義的iter沒有按照契約定義是否trival類型, 編譯時(shí)內(nèi)聯(lián)生成代碼時(shí)就不能找到屬性
2. 實(shí)際調(diào)用時(shí)通過重載來實(shí)現(xiàn), 不存在運(yùn)行時(shí)的開銷(struct __true_type{}, struct __false_type)
3. trivial類型不走ctor, copy, assign, dector, move直接使用memcpy, memmove等高效方式
4. 如何界定object是trivial, 滿足以下就是none trivial否則就是trivial
   a. 顯示定義構(gòu)造函數(shù)(ctor), 復(fù)制構(gòu)造函數(shù)(copy), 移動構(gòu)造(move), 賦值運(yùn)算符(assign), 析構(gòu)函數(shù)(dector)
   b. 類型有非POD(plain old data)類型成員
   c. 有虛函數(shù), 有基類

POD類型如下:

• 算數(shù)類型
• enum
• pointer(nullptr/object pointer/function pointer)
• 到類成員的指針類型 比如C類, M成員, C::M*
• pod類型組成的 class, struct, union

全局區(qū)間對象fill/copy (stl_uninitialized.h)

這里也是萃取了iter中是否為pod的類型優(yōu)化

    uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result) (萃取value pointer type)
      -> __uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result, _Tp*) (從Tp萃取is pod)
        -> 是pod , 調(diào)用algo_base的 _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result)
        -> 不是pod foreach調(diào)用stl_contruct中的構(gòu)建方法 for(***) _Construct(&*__cur, *__first);

uninitialized_fill, uninitialize_fill_n等等都是這個(gè)思路

雙頂層內(nèi)存緩沖器

這里stg沒有使用stl標(biāo)準(zhǔn)的std::allocator, 而是使用內(nèi)部實(shí)現(xiàn)的高效std::alloc, 這里并沒有嚴(yán)格接口對其.
這里定義了內(nèi)部接口供內(nèi)部容器使用:

template<class _Tp, class _Alloc>
class simple_alloc {

public:
    static _Tp* allocate(size_t __n)
      { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
    static _Tp* allocate(void)
      { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
    static void deallocate(_Tp* __p, size_t __n)
      { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
    static void deallocate(_Tp* __p)
      { _Alloc::deallocate(__p, sizeof (_Tp)); }
};

具體實(shí)現(xiàn)__malloc_alloc_template和__default_alloc_template
其中__malloc_alloc_template沒啥東西只是對malloc的簡單封裝, 可以設(shè)置oom時(shí)的回調(diào)函數(shù)
以下重點(diǎn)分析__default_alloc_template.

設(shè)計(jì)要義&方法

• 解決什么問題
  在glibc中其實(shí)也是一樣的問題和思路, 針對client零亂大量的申請/釋放, 會形成一些列大小不一且不相連的使用內(nèi)存片段, 會產(chǎn)生出內(nèi)碎片的問題
• slot化
  和內(nèi)存分頁一個(gè)思路, 把memory分成不同chunk slot, 把請求離散標(biāo)準(zhǔn)化, 這樣就形成了一系列的slot, [8, 16, 24, 32, 40, ..., 120, 128] 當(dāng)需要5 byte時(shí), 向上對其使用8 byte的slot分配, 這樣slot內(nèi)的內(nèi)碎片均值為4. 但是slot是有邊界的, 當(dāng)申請>128 byte時(shí)直接使用__malloc_alloc_template, __default_alloc_template旨在解決小內(nèi)存大量零碎調(diào)用
• 全局緩充
  為了避免連續(xù)不同slot的調(diào)用還設(shè)置的全集緩存, 當(dāng)前slot不夠的直接從全局緩存出

• 釋放緩存
  釋放緩存時(shí)實(shí)際是歸還給了stg的內(nèi)存緩存池, 以便后續(xù)調(diào)用時(shí)再次申請
  圖示如下:

  
  

代碼詳情

  union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];    /* The client sees this.        */
  }; //union 用戶視角char*, 系統(tǒng)視角滿足當(dāng)前slot長度, 首地址指向一個(gè)slot chunk地址
static _Obj* __STL_VOLATILE _S_free_list[] //全局slot, 每一個(gè)元素指向slot鏈表
 static void* allocate(size_t __n)
  {
    void* __ret = 0;
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n); // -> __malloc_alloc_template
    }
    else {
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n); //_S_freelist_index(__n)依據(jù)申請找到合適slot
      // 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));//申請內(nèi)存
      else {
        *__my_free_list = __result -> _M_free_list_link; //以前以后緩存, 拔出第一片返回, 回寫下一原有free到_S_free_list[x](*__my_free_list <-)
        __ret = __result;
      }
    }
    return __ret;
  };

同樣deallocate把歸還內(nèi)存按照slot插入到起始

  static void deallocate(void* __p, size_t __n)
  {
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n); // free
    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; //把用戶歸還內(nèi)存接上
      *__my_free_list = __q; //回寫_S_free_list對應(yīng)slot
      // lock is released here
    }
  }

重點(diǎn)是_S_refill和_S_chunk_alloc, 只要調(diào)入_S_refill一定是內(nèi)存當(dāng)前slot內(nèi)存不夠了
_S_refill調(diào)用_S_chunk_alloc分配足量內(nèi)存, 串聯(lián)slot內(nèi)鏈表結(jié)構(gòu).
_S_chunk_alloc 分配足夠了內(nèi)存, 具體如何足量下面有解釋

/* 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); //調(diào)用一個(gè)__n size chunk, 可以返回多個(gè),   返回內(nèi)存劃分:[__chunk, __chunk + __n*nobjs][free_start, free_end]
    _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);//只夠一個(gè)就地返回

    /* Build free list in chunk */ 
      __result = (_Obj*)__chunk;
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); //返回客戶端的
      for (__i = 1; ; __i++) { //構(gòu)建鏈表
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0; //結(jié)尾為空
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

_S_chunk_alloc的責(zé)任是分配給足量的內(nèi)存, 把內(nèi)存切分一部分給slot緩存, 一部分全局緩存.
client需求一個(gè)__n的內(nèi)存, 足量體現(xiàn)在:

• _S_chunk_alloc看全局緩存余量是否夠20__n, 如果夠一次劃給slot20__n
• _S_chunk_alloc看全局緩存余量[1__n, 不足20__n], 一次劃給最大的最大數(shù)目__n大小
• _S_chunk_alloc按照需求內(nèi)存220__n + left_space >> 4, 把20*__n劃給slot, 這個(gè)體現(xiàn)在返回__nobjs和_S_start_free的設(shè)置, 這部分代碼相對多一些

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); //夠20
    } else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result); //夠至少一個(gè), 有多少給多少slot
    } 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) {   //把余下全局緩沖區(qū)掛入__bytes_left緩沖區(qū)
            _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; //_S_start_free當(dāng)slot接到_S_free_list中
            *__my_free_list = (_Obj*)_S_start_free; //回寫_S_free_list
        }
        _S_start_free = (char*)malloc(__bytes_to_get);
        if (0 == _S_start_free) { //當(dāng)內(nèi)存不足時(shí)
            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; //在上面之前全局緩存已經(jīng)掛入slot
                    _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.如果還是走到這里報(bào)出內(nèi)存不足的錯(cuò)誤
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;//整塊[_S_start_free, _S_end_free] 下載遞歸調(diào)用, 劃分slot
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

調(diào)用示例

假如slot目前為空

• call a(6)

• call a(128)

• call a(128)

• call d(8)

有此看出:

1. 專注小內(nèi)存分配, 大內(nèi)存交給malloc
2. 把小內(nèi)存劃分離散的slot, 有點(diǎn)像一些列的齒輪, 齒比是8字節(jié)間隔, 看需求咬合那個(gè)最合適
3. slot要一次申請多個(gè), 能夠就給slot緩存, 這樣避免了多次小內(nèi)存申請
4. 再設(shè)置一級全局緩存, 補(bǔ)充空的slot內(nèi)存需求
5. 當(dāng)內(nèi)存不足時(shí)考慮了, 把全局內(nèi)存歸并slot, 利用現(xiàn)有slot化解, 如果不能化解報(bào)錯(cuò)
6. 當(dāng)free內(nèi)存時(shí), 不是真正free, 按照slot放回, 減少系統(tǒng)調(diào)用, 下次再需要直接返回
7. slot 存儲overhead為0, 使用union, 系統(tǒng)視角一個(gè)指針指向next free slot, 用戶視角為未初始化內(nèi)存

示例

下面以常用vector示例看下如何使用內(nèi)存分配機(jī)制

vector代碼片段如下:

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
  // requirements:

  __STL_CLASS_REQUIRES(_Tp, _Assignable);

private:
  typedef _Vector_base<_Tp, _Alloc> _Base;

define __STL_DEFAULT_ALLOCATOR(T) alloc  // 配置在stl_config.h 
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; //默認(rèn)是沒有__USE_MALLOC, alloc使用上述__default_alloc_template分配

//vector base代碼片段
template <class _Tp, class _Alloc> //__default_alloc_template
class _Vector_base {
public:
  typedef _Alloc allocator_type; //__default_alloc_template
  allocator_type get_allocator() const { return allocator_type(); }

  _Vector_base(const _Alloc&)
    : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  _Vector_base(size_t __n, const _Alloc&)
    : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  {
    _M_start = _M_allocate(__n);
    _M_finish = _M_start;
    _M_end_of_storage = _M_start + __n;
  }


  ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }

typedef simple_alloc<_Tp, _Alloc> _M_data_allocator; // 用上述simple_alloc做接口, 傳入__default_alloc_template實(shí)現(xiàn)類型
  _Tp* _M_allocate(size_t __n)
    { return _M_data_allocator::allocate(__n); } //調(diào)入內(nèi)存分配

假如有如下代碼

auto v = vector<int>(3,0);
for (auto i = 4; i < 8; ++i){
  emplace_v = vector<int>(i, 0);
}

v申請43(size(int)v.size()) 12 bytes, 歸并申請到16字節(jié)

emplace_v(i = 4)申請4*4后, 直接使用free list

emplace_v釋放后, 插入slot 16首位

emplace_v(i = 5)申請4*5后, 使用slot 24, 從全局free分配, 分配10個(gè)

emplace_v釋放后 slot 16歸還

emplace_v (i = 6)申請46和上一輪情況相同
emplace_v (i = 7)申請47, 使用slot 30, 全局為空, 申請

emplace_v釋放4*7

reference:

https://github.com/arkingc/note/blob/master/C%2B%2B/STL%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.md#4stl%E5%85%AD%E5%A4%A7%E9%83%A8%E4%BB%B6
https://backendhouse.github.io/post/stl%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-traits/
https://stackoverflow.com/questions/51659101/why-can-static-data-member-not-be-initialized-in-class-in-c11