我們在之前的文章學(xué)習(xí)了編寫malloc_allocator，它是一個借助malloc分配內(nèi)存的分配器，并且實現(xiàn)了在C++11標準中的接口。同時malloc_allocator可以幫助我們實現(xiàn)另一個分配器free_list_allocator。

free_list_allocator是我們整個項目真正要使用的分配器。在說明具體的代碼之前，先來說說為什么要用分配器而不直接使用 new 與 delete 進行內(nèi)存的分配與釋放。如果有學(xué)習(xí)過操作系統(tǒng)的相關(guān)知識的話應(yīng)該有所了解: 頻繁的進行內(nèi)存申請時將產(chǎn)生大量的內(nèi)存碎片且降低性能。

舉個例子， 假設(shè)我們有10個單位的連續(xù)內(nèi)存區(qū)域，范圍 0 - 9。我們首先申請 4 個單位的空間， 那么將分配區(qū)域 0 - 3。然后我們再申請 4 單位內(nèi)存， 分配區(qū)域 4 - 7?，F(xiàn)在我們只有8 - 9的位置是空閑的， 然而如果以后申請的內(nèi)存都大于 2 個單位, 那么只能從別的內(nèi)存段分配內(nèi)存，區(qū)域 8 - 9永遠用不上了，成為碎片。

為了避免碎片的產(chǎn)生，我們才使用分配器定義容器的分配策略。那么分配器采用什么方法避免內(nèi)存碎片的產(chǎn)生呢？malloc_alloctor雖說是分配器，但它只是簡單的封裝了malloc()函數(shù)進行內(nèi)存分配而已.。 malloc()對偶發(fā)的大量內(nèi)存分配做了優(yōu)化，所以此時malloc_alloctor的效率良好。然而在需要頻繁分配少量內(nèi)存的情況下效率低下，且容易產(chǎn)生內(nèi)存碎片。

有鑒于此，在這一情況下，人們常使用基于內(nèi)存池的分配器來解決頻繁少量分配問題。與默認的“按需分配”方式不同，在使用基于內(nèi)存池的分配器時，程序會預(yù)先為之分配大塊內(nèi)存（即“內(nèi)存池”），而后在需要分配內(nèi)存時，自定義分配器只需向請求方返回一個指向池內(nèi)內(nèi)存的指針即可；而在對象析構(gòu)時，并不需實際解除分配內(nèi)存，而是延遲到內(nèi)存池的生命周期完結(jié)時才真正解除分配。這樣不僅能減少內(nèi)存碎片的產(chǎn)生也避免了對系統(tǒng)頻繁的內(nèi)存申請。

我們要實現(xiàn)free_list_allocator正是此類分配器。free_list_allocator的整體思想是: 如果要分配的內(nèi)存大于 128 bytes（即分配大量內(nèi)存) ，就交給malloc_allocator處理。否則由 memory pool(內(nèi)存池) 負責(zé)分配與回收。

我們先來了解free_list_allocator的聲明:

template<typename T>
class free_list_allocator
{
private:
    static const std::size_t ALIGN = 8;
    static const std::size_t MAX_BLOCK_SIZE = 128;
    static const std::size_t FREE_LIST_NUM = MAX_BLOCK_SIZE / ALIGN;

    struct obj
    {
        obj *free_list_link;
    };

    static obj *free_list[FREE_LIST_NUM];
    //內(nèi)存池起始位置
    static char *start_pool;
    //內(nèi)存池結(jié)束位置
    static char *end_pool;
    static std::size_t heap_size;


    //將byte上調(diào)至8的倍數(shù)
    static std::size_t round_up(std::size_t byte)
    {
        return ((byte) + ALIGN - 1) & ~(ALIGN - 1);
    }

    //由所需內(nèi)存大小決定free_list的索引
    static std::size_t free_list_index(std::size_t byte)
    {
        return  byte / (ALIGN + 1);
    }

    //為free_list加入新的塊
    static T *refill(std::size_t block_size);

    //分配 num 個 block_size 的空間
    static char *chunk_alloc(std::size_t block_size, std::size_t& num);


public:
    typedef T value_type;

    free_list_allocator() {}
    template<typename U>
    free_list_allocator(const free_list_allocator<U>&) {}

    static T *allocate(std::size_t num);
    static void deallocate(T *p, std::size_t num);
};


template<typename T>
typename free_list_allocator<T>::obj *
free_list_allocator<T>::free_list[FREE_LIST_NUM] = {
    0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0
};


template<typename T>
char *free_list_allocator<T>::start_pool = nullptr;

template<typename T>
char *free_list_allocator<T>::end_pool = nullptr;

template<typename T>
std::size_t free_list_allocator<T>::heap_size = 0;

free_list_allocator的核心有兩部分： free_list 與 memory pool， free_list 從 memory pool 中獲取空間并添加內(nèi)存塊。那么所謂的free_list到底是什么？

struct obj
{
    obj *free_list_link;
};

static obj *free_list[FREE_LIST_NUM];

free_list 被聲明為一個大小為 FREE_LIST_NUM 的數(shù)組， 且數(shù)組元素為一個指向 struct obj 的指針。實際上每個 free_list 的元素分別指向區(qū)塊大小為 8, 16, 24, 32, 40, 48 ..... 120, 128 的鏈表。

free_list 示意圖

上圖只顯示了8個free_list（實際有16個）。按照之前所說，3號free_list 指向大小為 32 bytes 的內(nèi)存塊。其中每個內(nèi)存塊的開始部分儲存一個 obj 結(jié)構(gòu)，每個 obj 都有一個指向下一個內(nèi)存塊的指針（即 free_list_link）。每當(dāng)用戶需要申請內(nèi)存時， free_list_allocator 便從free_list中找到相應(yīng)大小的塊并且以返回內(nèi)存塊首地址的方式分配出去（即 obj 的地址）。

再了解了 free_list_allocator 的基本原理后，我們終于能看看具體實現(xiàn)了。

1. free_list_index(std::size_t byte)

//由所需內(nèi)存大小決定free_list的索引
static std::size_t free_list_index(std::size_t byte)
{
    return  byte / (ALIGN + 1);
}

free_list_index 用來查找目標 free_list 的索引。比如需要 20 字節(jié)的內(nèi)存時我們應(yīng)該去 free_list[ 2 ] 中取得內(nèi)存塊。

2. allocate(std::size_t num)

template<typename T>
T *free_list_allocator<T>::allocate(std::size_t num)
{   
    if (num * sizeof(T) > MAX_BLOCK_SIZE) {
        return malloc_allocator<T>::allocate(num);
    }

    obj *result;
    auto target_free_list = free_list + free_list_index(num * sizeof(T));
    result = *target_free_list;
    
    if (result == nullptr) {
        return refill(round_up(num * sizeof(T)));
    }

    //將free_list內(nèi)的元素指向第2個內(nèi)存塊
    *target_free_list = result->free_list_link;
    return reinterpret_cast<T*>(result);
}

同樣， allocate(num) 負責(zé)分配 num 個元素的內(nèi)存。 它首先計算所需總內(nèi)存是否大于最大塊的大?。?28 bytes），如果是的話就調(diào)用 malloc_allocator<T>::allocate 分配內(nèi)存。想想之前提過的， malloc 適合進行大量內(nèi)存的分配。然后借助 free_list_index 找到具有合適大小的塊的 free_list。

接著對target_free_list解除引用獲取第一個內(nèi)存塊的地址。如果 result == nullptr, 則說明此 free_list 為空，沒有指向的內(nèi)存塊。此時我們需要調(diào)用 refill() 重新為這個 free_list 添加內(nèi)存塊。（refill 的具體實現(xiàn)要留到下次了）

如果我們成功獲取第一個內(nèi)存塊的地址話， 我們還需要將 free_list 的指針重新設(shè)置為第二個內(nèi)存塊的地址（這個時候第二個內(nèi)存塊就變成第一個了）。最后再類型轉(zhuǎn)換返回結(jié)果就行了。

調(diào)用 allocate 前

調(diào)用 allocate 后

3. deallocate(T *p, std::size_t num)

template<typename T>
void free_list_allocator<T>::deallocate(T *p, std::size_t num)
{
    /*
    p為需要回收的內(nèi)存區(qū)域的首指針，num代表區(qū)域內(nèi)元素的個數(shù)
    */

    std::size_t size = num * sizeof(T);
    if (size > MAX_BLOCK_SIZE) {
        malloc_allocator<T>::deallocate(p, num);
        return;
    }
    
    //被回收的內(nèi)存將被加入target_free_list指向的鏈表
    auto target_free_list = free_list + free_list_index(size);
    obj *target_block = reinterpret_cast<obj*>(p);
    target_block->free_list_link = *target_free_list;
    *target_free_list = target_block;
}

deallocate 的思想與 allocate 對應(yīng)：allocate 是獲取第一個內(nèi)存塊，將 free_list 指向第二個內(nèi)存塊。而 deallocate 把需要回收的內(nèi)存塊指向當(dāng)前第一個內(nèi)存塊，將free_list 指向這個被回收的塊。

調(diào)用 deallocate 前

調(diào)用 deallocate 回收后

我們現(xiàn)在已經(jīng)可以使用 allocate 與 deallocate 分配釋放內(nèi)存，但還有 refill(）和 chunk_alloc() 沒有實現(xiàn)。限于文章的篇幅，那就只能等到下次了。再見~

下一篇： STL in C++11 (Allocator 5)

最后附上本篇文章的代碼地址：free_list_allocator.h

以及github地址：https://github.com/Puppas/STL-in-Cpp11