記憶體配置設定器 SGI alloca分析

     ~~~~     之前我們了解了一些基礎的東西，我們下面來學習一下stl裡面的經典，我們隻學習SGI，關于源碼，後面整理上傳到gihub吧。

SGI STL首頁：http://www.sgi.com/tech/stl/index.html

STLport首頁：http://www.stlport.org/

找到的源碼，SGI源碼，感謝開源：

https://github.com/karottc/sgi-stl

https://github.com/CaesarTang/STL

     ~~~~     我們先看看SGI的對于記憶體的配置和釋放的設計哲學：

向system heap要求空間

考慮多線程（multi threads）狀态

考慮記憶體不足時的應變措施

考慮過多“小型區塊”可能造成的記憶體碎片（fragment）問題。

     ~~~~     為了不把問題複雜化，我下面寫的會比較簡單，而且暫時移除多線程狀态處理，我們要先入門才行。

     ~~~~     C++記憶體配置和釋放基本操作就是new和delete，在C裡面就相當于malloc和free函數，而我們學習的SGI使用的正式malloc和free完成記憶體配置和釋放。

     ~~~~     就像我們之前說小型塊記憶體會造成記憶體碎片的問題，SGI就有為此設計了雙層配置器，第一輯配置器直接使用malloc和free，而第二級配置器視情況采用不同的政策。

     ~~~~     當配置區塊超過128bytes時，視為足夠大，調用第一級配置器；當配置區塊小于128bytes時，視為過小，為了降低額外負擔（overhead），便采用複制的memory pool整理方式，而不再求助于第一級配置器，整個設計到底使用哪一個級别的配置器，取決于__USE_MALLOC是否被定義；

     ~~~~     找了一下SGI的stl_alloca.h的源碼，github上面有人上傳了，關于選擇一級配置器和二級配置器的地方。

...
// SGI STL 第一級配置器
// 無 “template 類型參數”，“非類型參數 __inst”，完全沒有用
template <int __inst>
class __malloc_alloc_template {
...
};
...
typedef __malloc_alloc_template<0> malloc_alloc;
...
template <bool threads, int inst>
class __default_alloc_template {
...
}
...
# ifdef __USE_MALLOC
typedef malloc_alloc alloc;  // 令 alloc 為第一級配置器
...
# else
...
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;  // 令 alloc 為第二級配置器
...
# endif
           

可以明顯的看到__malloc_alloc_template就是一級配置器，__default_alloc_template就是二級配置器，我們也可以看到，它們都不接受任何template參數，是以它們不符合STL規格，SGI需要為它包裝一個接口，用來符合STL規格：

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)); }
};
           

第一級擴充卡

     ~~~~     在SGI中第一級擴充卡為__malloc_alloc_template，我們直接看代碼解釋

//malloc-based allocator. 通常比稍後介紹的default alloc速度慢
//一般而言是thread-safe，并且對于空間的運用比較搞笑
//一下是第一級擴充卡
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)();
#endif

public:

  static void* allocate(size_t __n)
  {
    void* __result = malloc(__n);    //一級擴充卡直接使用malloc
    //無法滿足需求時
    if (0 == __result) __result = _S_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
    //無法滿足需求時，改用_S_oom_realloc
    if (0 == __result) __result = _S_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，有待客端設定
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#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;
        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>::_S_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) { __THROW_BAD_ALLOC; }
        (*__my_malloc_handler)();    //調用處理例程，企圖釋放記憶體
        __result = realloc(__p, __n);//再次嘗試配置記憶體
        if (__result) return(__result);
    }
}

//注意以下直接将參數inst指定位 0
typedef __malloc_alloc_template<0> malloc_alloc;
           

     ~~~~     第一級擴充卡以malloc，free，relloc等C函數執行實際的記憶體配置，是否，重配置操作，并實作出類似C++new-handler的機制，是的，它不能直接運用C++new-handler機制，因為它并非使用new來配置記憶體。

     ~~~~     所謂C++new-handler機制是，你可以要求系統在記憶體配置需求無法被滿足時，調用一個你所指定的函數，換句話說，一旦new無法完成任務，在丢出__THROW_BAD_ALLOC異常狀态之前，會先調用由客端指定的處理例程，改處理例程通常即被稱為new-handler，new-handler解決記憶體不足的做法有特定的模式。

     ~~~~     注意，設計記憶體不足處理例程是客端的責任，設定記憶體不足處理例程，也是客端責任，再一次提醒你，記憶體不足處理例程解決問題的做法有着特定的模式。

第二級擴充卡

     ~~~~     第二級擴充卡多了一些機制，避免太多小額區塊造成記憶體碎片，小額區塊帶來的其實不僅僅是記憶體碎片，配置時的額外負擔也是一個大問題，額外負擔永遠無法避免，畢竟系統要靠這多出來的空間來管理記憶體，如圖2-3所示，但是區塊俞小，額外負擔所占比例就愈大，愈顯得浪費。

     ~~~~     SGI第二級擴充卡的做法是，如果區塊足夠大沒超過128bytes時，就移交給第一擴充卡處理，當區塊小于128bytes時，則以記憶體池管理，此法又稱為次層配置，每次配置一大塊記憶體，并維護對應之自由連結清單free-list，下次若再有相同大小的記憶體需求，就直接從free-list中拔出。如果客端是更小的區塊，就由配置器回收到free-list中，同時SGI會主動将小額區塊的記憶體需求上調到8的倍數，同時維護這16個free-list，各自管理大小分别為8,16,24,32,40,48,56,64…128bytes的小額區塊，free-list的節點結構如下

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

     ~~~~     第一次看到這個共同體我是沒有了解書寫者的意圖的，知道看完二級擴充卡的代碼，我才覺得這裡的正确性，回到stl解析的一句話，stl裡面的源代碼寫得比你甚至是大多數人都要好。

     ~~~~     下面我們來看源碼

//下面是二級配置器
//注意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  free_list的個數
# endif
//_S_round_up将bytes上調至8的倍數
  static size_t
  _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

__PRIVATE:
  union _Obj {//free-list的節點構造
        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
    //16個free-list
    static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
# endif
//以下函數根據區塊大小，決定使用第n号free-list，n從 起算
  static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }
  //傳回一個大小為n的對象，并可能加入大小為n的其他區塊到free-list
  static void* _S_refill(size_t __n);
  //配置一大塊空間，可以容納__nobjs個大小為__size的區塊
  //如果配置__nobjs個區塊有所不便，__nobjs可能會降低
  static char* _S_chunk_alloc(size_t __size, int& __nobjs);

  // Chunk allocation state.
  static char* _S_start_free;    //記憶體池起始位置，隻在_S_chunk_alloc中變化
  static char* _S_end_free;      //記憶體池結束位置，隻在_S_chunk_alloc中變化
  static size_t _S_heap_size;
  
public:

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

  /* __p may not be 0 */
  static void deallocate(void* __p, size_t __n);

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

} ;
           

     ~~~~     我們下面來着重分析其中的幾個函數

     ~~~~     第一個allocate，記憶體配置函數，身為一個配置器，__default_alloc_template 擁有配置器的标準接口函數allocate，次函數首先判斷區塊大小，大于128的就調用第一級擴充卡，小于就調用對應的free-list，如果free-list有可用的區塊，就直接拿來用，如果沒有就調用_S_refill為free-list重新填充空間，_S_refill這個函數我們後面介紹。

     ~~~~     在這裡如果free-list的16連結清單中對應的連結清單裡可用的區塊，就取對應連結清單的首個區塊，同時将區塊移除連結清單，free-list對應直線的首位址，向連結清單後移；然後我們後面就會發現，當釋放區塊的時候，同樣區塊插入的位置也是連結清單首部，這其實就是一個棧，16個free-list就是16個棧。

// __n必須大于0 
  static void* allocate(size_t __n)
  {
    void* __ret = 0;
    //大于128就調用第一配置器
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      //尋找16個free-list中适當的一個
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __RESTRICT __result = *__my_free_list;
      if (__result == 0)
        //沒有找到可用的free-list，準備重新填充free-list
        //同時擷取一個申請好的符合要求的區塊
        __ret = _S_refill(_S_round_up(__n));
      else {
        //調整free-list
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }
    return __ret;
  };
           

     ~~~~     第二個函數deallocate，空間釋放函數，作為為一個擴充卡，同樣擁有擴充卡标準接口函數deallocate。該函數首先判斷區塊大小，大于128bytes就調用第一級擴充卡，小于128bytes就找到對應的free-list，将區塊收回。

     ~~~~     如果小于128bytes的區塊，我們就是直接插入到對應free-list對應連結清單的首部。

// __p必須不為空
  static void deallocate(void* __p, size_t __n)
  {
    //大于128就調用第一配置器
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
      //尋找對應的free-list
      _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
    }
  }
           

     ~~~~     下面就是重新填充函數_S_refill，當沒有可用的區塊時，就調用_S_refill，準備為free-list重新填充空間，新的空間将取自記憶體池，經由_S_chunk_alloc函數完成（下面會繼續講）,預設得到20個新的節點，但是如果記憶體池不足，可能擷取的節點數小于20，這裡要注意__nobjs是引用傳進去的。

//傳回一個大小為__n的對象，并且有時候會為适當的free-list增加節點
//假設__n已經适當調節至8的倍數，這了的__n必須先進行調節
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    //調用_S_chunk_alloc，嘗試取得__nobjs個區塊作為free-list的新節點
    //注意參數__nobjs是通過引用傳遞到_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;

    //如果隻擷取到了一個區塊，這個區塊就配置設定給調用者用，free-list無新節點
    if (1 == __nobjs) return(__chunk);
    //否則準備調整free-list，納入新節點，重新擷取free-list的位置
    __my_free_list = _S_free_list + _S_freelist_index(__n);

    //在__chunk空間中建立free-list
      __result = (_Obj*)__chunk;//這一塊傳回給客端
      //以下導引free-list指向新配置的空間，第一個傳回給客端了是以需要+ __n
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
      //将free-list的各個節點串連起來
      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);//傳回配置好的區塊
}
           

     ~~~~     而從記憶體池中取空間給free-list使用，是_S_chunk_alloc做得事情：

//從記憶體池中取空間給free-list使用，是_S_chunk_alloc的工作
//主要負責在大塊中配置設定記憶體，防止記憶體碎片
//__size必須是上調到8的倍數，也就是記憶體對齊
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) {
      //空間不足以配置設定，但是足夠配置設定一個或以上的區塊，我們修改__nobjs為目前可配置設定最大值
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
      //當剩餘空間不足以配置設定哪怕一個__size大小的區塊
        size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        //先試着讓記憶體池裡面的殘餘零頭還有利用價值
        if (__bytes_left > 0) {
          //記憶體池内還有一些零頭，先配置設定給适當的free-list，先尋找适當的free-list
            _Obj* __STL_VOLATILE* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);
            //調整 free-list，将記憶體池中的殘餘空間編入
            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
        //配置 heap空間，用來補充記憶體池
        _S_start_free = (char*)malloc(__bytes_to_get);
        if (0 == _S_start_free) {
          //head空間不足，malloc失敗
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
	    _Obj* __p;
            //嘗試使用我們手上有的沒有使用的空間，就是那些還沒有被配置設定的
            //在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;
                    //遞歸自己，同時修正__nobjs
                    return(_S_chunk_alloc(__size, __nobjs));
                    //注意任何的殘餘零頭終被編入适當的free-list中備用
                }
            }
	          _S_end_free = 0;	// 到處都沒有記憶體可以使用了
            //調用一級擴充卡，看看out-of-memory機制是否能出力（new-handler）
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // 這裡會抛出異常，或者記憶體不足的情況獲得改善
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        //調用遞歸，修正__nobjs
        return(_S_chunk_alloc(__size, __nobjs));
    }
}
           

     ~~~~     上面的函數以_S_end_free和_S_start_free來判斷記憶體池的水量，如果水量充足，就直接調出20個區塊傳回給free-list，如果水量不足，但是足夠提供至少一個以上的區塊，就拔出這不足20各區塊的空間出去，這時候其引用傳遞的__nobjs就可以将實際的供應區塊數傳回到上一層。如果記憶體池中連一個區塊都無法提供，如果剩餘空間不為空，則将剩餘空間配置設定給free-list的其他可用的連結清單，然後去系統的heap中配置記憶體空間，為記憶體池注入記憶體以應付需求，新的記憶體申請大小為需求的兩倍加上一個配置次數而愈來愈大的附加量。