在書中介紹了有2個(gè)空間配置器：

• 第一個(gè)是適合直接用的malloc/free钾菊，簡單包裝了下蜀肘，并實(shí)現(xiàn)了類似C++ new-handler機(jī)制蔓钟。
• 第二個(gè)用的是一個(gè)建立在一個(gè)內(nèi)存池和free_list上面的次級(jí)配置器，實(shí)現(xiàn)了更靈活的內(nèi)存管理搂捧。

一級(jí)配置器

二級(jí)配置器

二級(jí)配置器多了些機(jī)制驮俗，避免了太多小額區(qū)塊造成的內(nèi)存碎片。整體做法是：如果區(qū)塊足夠大允跑，超128bytes 時(shí)王凑，就移交第一級(jí)配置器處理搪柑，當(dāng)區(qū)塊小于128bytes時(shí)，則以內(nèi)存池管理索烹。

二級(jí)配置器整體配置如圖：

二級(jí)空間配置器.jpg

內(nèi)存池就是從堆中申請(qǐng)的大塊的內(nèi)存工碾，負(fù)責(zé)填充free_list。內(nèi)存池直接由malloc分配术荤，用2個(gè)指針表示，start_free指針表示當(dāng)前內(nèi)存池剩余內(nèi)存的起始地址每篷。

內(nèi)存池.jpg

free_list

union obj 
{
    union obj *free_list_link;
    char client_data[1];    // 沒什么用
};

enum {  _ALIGN = 8  };    // 小型區(qū)塊下限
enum {  _MAX_BYTES = 128  };    // 小型區(qū)塊上限
enum {  _NFREELISTS = _MAX_BYTES / _ALIGN  };  // free_list 個(gè)數(shù)

free_list是指針數(shù)組瓣戚。每一個(gè)數(shù)組槽內(nèi)指向的是一個(gè)由指定大小的內(nèi)存塊連接起來的list〗苟粒客戶申請(qǐng)內(nèi)存子库，就將其中相應(yīng)的內(nèi)存從list"拔下"，客戶歸還內(nèi)存則就內(nèi)存插入相應(yīng)的list中矗晃。

free_list.jpg

空間配置器

class alloc 
{
    private:
        static obj* free_list[_NFREELISTS];      // obj數(shù)組
    private:
        static char *start_free;    // 內(nèi)存池起始位置
        static char *end_free;      // 內(nèi)存池結(jié)束位置
        static size_t heap_size;
    private:
        /*  將bytes上調(diào)至8的倍數(shù)  */
        static size_t ROUND_UP(size_t bytes) 
        {  
            return (((bytes) + _ALIGN - 1) & ~(_ALIGN - 1)); 
        }

        /*  根據(jù)區(qū)塊大小使用第n號(hào)free_list  */
        static size_t FREELIST_INDEX(size_t bytes) 
        {  
            return (((bytes) + _ALIGN - 1) / _ALIGN - 1);  
        }
        
        /*  為free_list某個(gè)大小的list增加節(jié)點(diǎn)  */
        static void *refill(size_t n);

        static char *chunk_alloc(size_t size, int &nobjs);
    public:
        static void *allocate(size_t n);
        static void deallocate(void *p, size_t n);
        static void *reallocate(void *p, size_t old_size, size_t new_size);
};

• 空間配置函數(shù)

void* alloc::allocate(size_t n) 
{  
    obj **my_free_list, *list;
    if (n > (size_t) _MAX_BYTES)    // 當(dāng)需要的內(nèi)存大于某個(gè)節(jié)點(diǎn)仑嗅，就調(diào)用malloc
        return malloc(n);

    my_free_list = free_list + FREELIST_INDEX(n);    // 指向第n號(hào)list
    list = *my_free_list;
    
    if (list) {
        *my_free_list = list->free_list_link;    // 從list頭部"拔出一個(gè)內(nèi)存"，返回給客戶
        return list;
    } else        
        return refill(ROUND_UP(n));    // 如果當(dāng)前l(fā)ist為空张症，則重新申請(qǐng)內(nèi)存填充該list
}

• 空間釋放函數(shù)

void alloc::deallocate(void *p, size_t n) 
{
    obj *q = (obj *) p;
    obj **my_free_list;
    
    if (n > (size_t)_MAX_BYTES)    // 當(dāng)需要的內(nèi)存大于某個(gè)節(jié)點(diǎn)仓技，就調(diào)用free
        free(p);
    else {            // 當(dāng)需要的內(nèi)存小于某個(gè)節(jié)點(diǎn)，就將其保存至某個(gè)list下
        my_free_list = free_list + FREELIST_INDEX(n);    // my_free_list指向第n號(hào)list
        q->free_list_link = *my_free_list;  
        *my_free_list = q;
    }
}

• 從內(nèi)存池取出內(nèi)存供給free list使用

chunk_alloc.png

// 從內(nèi)存池取出空間給free_list使用(第n號(hào))(假定size已經(jīng)適當(dāng)調(diào)整為8的倍數(shù))
char *alloc::chunk_alloc(size_t size, int &n_objs) 
{    
    char *result;
    size_t total_bytes = size * n_objs;              // 需要的內(nèi)存總量
    size_t bytes_left = end_free - start_free;       // 內(nèi)存池剩余空間

    if (bytes_left >= total_bytes) {
        // 內(nèi)存池剩余空間空間完全滿足需要
        result = start_free;
        /* 更新start_free指針 */
        start_free += total_bytes;

        return result;
    } else if (bytes_left >= size) {
        // 內(nèi)存池剩余空間不能完全滿足需求量,但足夠供應(yīng)一個(gè)(含)以上的區(qū)塊
        n_objs = bytes_left / size;    // 計(jì)算可以供應(yīng)幾個(gè)區(qū)塊
        /* 更新start_free指針 */
        total_bytes = n_objs * size;
        result = start_free;
        start_free += total_bytes;

        return result;
    } else {
        // 內(nèi)存池剩余空間連一個(gè)區(qū)塊的大小都不滿足
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // 試著讓內(nèi)存池中殘余零頭還有利用價(jià)值
        if ( bytes_left > 0 ) {
            // 將內(nèi)存池殘余內(nèi)存配給適當(dāng)?shù)膄ree_list(更小的size的list);
            obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *) start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj *) start_free;
        }
        // 配置heap空間, 用來補(bǔ)充內(nèi)存池
        start_free = (char *) malloc(bytes_to_get);
        if (nullptr == start_free) {
            obj *p, **my_free_list;
            // heap空間不足,搜尋適當(dāng)?shù)膄ree_list("未用區(qū)塊,且區(qū)塊夠大")
            for (int i = size; i <= _MAX_BYTES; i += _ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) {
                    *my_free_list = p->free_list_link;
                     start_free = (char *)p;
                     end_free = start_free + i;
                     return chunk_alloc(size, n_objs);
                }
           }
           end_free = 0;
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        
        return chunk_alloc(size, n_objs);
   }
}

參考資料
[1] 《STL源碼剖析》侯捷