STL空间配置

SGI STL有两级配置器：

• 第一级配置器的allocate() 和 realloc()都是在调用malloc() 和 realloc()不成功后，改调用oom_malloc() 和 oom_realloc()，后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存来完成任务，但如果“内存不足处理例程”未被客端设定，oom_malloc() 和 oom_realloc()便调用__THROW_BAD_ALLOC，丢出bad_alloc异常信息，或利用exit(1)终止程序；

• 第二级配置器多了一些机制，避免太多小额区块造成内存的碎片：

  • 如果区块够大，超过128bytes，就移交第一级配置器处理
  • 当区块小于128bytes，则以内存池管理，此法又称作次层配置：
    
    • 每次配置一大块内存，并维护对应的自有链表，下次再有相同大小的内存需求，就直接从free-list中拨出；
    • 如果客端释放小额区块，就由配置器回收到free-list中；

以下代码为简单实现：

第一级配置器头文件：malloc_alloc.h

#ifndef MALLOC_ALLOC_H
#define MALLOC_ALLOC_H
#include<stdlib.h>

class malloc_alloc{
private:
    //这两个函数处理内存不足的情况
    static void* oom_malloc(size_t n);
    static void* oom_realloc(void* p, size_t n);
public:
    static void* allocate(size_t n){
        void* result = malloc(n);
        if (result == 0)result = oom_malloc(n);
        return result;
    }

    static void deallocate(void* p, size_t n){
        free(p);   //n 其实完全没有用上
    }

    static void* reallocate(void* p, size_t old_sz, size_t new_sz){
        void* result = realloc(p, new_sz);
        if (result == 0)result = oom_realloc(p, new_sz);
        return result;
    }
};
#endif

第一级配置器头文件：malloc_alloc.cpp

#include"malloc_alloc.h"
#include<iostream>

void* malloc_alloc::oom_malloc(size_t n){
    void* result = 0;
    int i = 0, j = 0;

    //不停的尝试释放，配置，再释放，再配置
    for (; i < 100000; i++){
        j = 0;
        while (j < 100000)j++;

        result = malloc(n);
        if (result)return result;
    }

    std::cout << "malloc error!" << std::endl;
    return 0;
}

void* malloc_alloc::oom_realloc(void* p, size_t n){
    void* result = 0;
    int i = 0, j = 0;
    for (; i < 100000; i++){
        j = 0;
        while (j < 100000)j++;

        result = realloc(p, n);
        if (result)return result;
    }
    std::cout << "realloc error!" << std::endl;
    return 0;
}

第二级配置器头文件：memorypool.h

#ifndef _MEMORYPOOL_H
#define _MEMORYPOOL_H
#include<iostream>
using namespace std;

enum {ALIGN = 8}; //小型区块的上调边界
enum {MAX_BYTES = 128};  //小型区块的上限
enum {NUMFREELISTS = MAX_BYTES / ALIGN}; //freelists个数

//内存池
class Alloc{
private:
    //freelist的节点构造
    union obj{
        union obj* free_list_link;
        char client_data[1];
    };
private:
    //16个freelists
    static obj* volatile free_list[NUMFREELISTS];

    //以下函数根据区块的大小，决定使用第n号free_list，n从0开始
    static size_t FREELIST_INDEX(size_t bytes){
        return ((bytes + ALIGN - 1) / ALIGN - 1);   
    }

    //将bytes上调至8的倍数
    static size_t ROUND_UP(size_t bytes){
        return (((bytes)+ALIGN - 1) & ~(ALIGN - 1));
    }

    //返回一个大小为n的对象，并可能加入大小为n的其他区块到free_list
    static void* refill(size_t n);

    //配置一大块区间，可容纳nobjs个大小为size的区块，如果修饰nobjs个区块无法满足，
    //nobjs可能会降低
    static char* chunk_alloc(size_t size, int& nobjs);

    //区块的状态
    static char* start_free;  //内存池的起始地址
    static char* end_free;    //内存池的结束地址
    static size_t heap_size;   

public:
    static void* allocate(size_t n); //分配指定大小的内存
    static void deallocate(void* p, size_t n);  //回收指定内存
    static void* reallocate(void* p, size_t old_sz, size_t new_sz); //重新分配内存
};
#endif

第二级配置器头文件：alloc.cpp

#include"malloc_alloc.h"
#include"memorypool.h"

//static成员的初值设定
char* Alloc::start_free = NULL;
char* Alloc::end_free = NULL;
size_t Alloc::heap_size = 0;
Alloc::obj* volatile Alloc::free_list[NUMFREELISTS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

//分配内存
void* Alloc::allocate(size_t n){
    obj* volatile *my_free_list;
    obj* result;

    //大于128就调用malloc_alloc
    if (n > 128)return malloc_alloc::allocate(n);

    //寻找16个free_list中最合适的一个
    my_free_list = free_list + FREELIST_INDEX(n);

    result = *my_free_list;
    if (result == 0){
        //没有可用的free_list，准备重新填充free_list
        void* r = refill(ROUND_UP(n));
        return r;
    }
    //调整free_list
    *my_free_list = result->free_list_link;
    return result;
}

//释放内存
void Alloc::deallocate(void* p, size_t n){
    obj* q = (obj*)p;
    obj* volatile* my_free_list;

    //大于128就调用malloc_deallocate
    if (n > 128){
        malloc_alloc::deallocate(p, n);
        return;
    }

    //寻找对应的区块
    my_free_list = free_list + FREELIST_INDEX(n);
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

//返回一个大小为n的对象，并且有时候会为适当的free_list增加节点，假设n已经适当上调至8的倍数
void* Alloc::refill(size_t n){
    int nobjs = 3;
    //调用chunk_alloc()，尝试取得nobjs个区块作为free_list的新节点，注意参数nobjs是pass by reference
    char* chunk = chunk_alloc(n, nobjs);
    obj* volatile* my_free_list;
    obj* result;
    obj *current_obj, *next_obj;
    int i;

    //如果只获得一个区块，这个区块就分配给调用者，free_list无新节点
    if (nobjs == 1)return (chunk);


    //否则准备调整free_list，纳入新节点
    my_free_list = free_list + FREELIST_INDEX(n);

    result = (obj*)chunk;  //这一块准备返回给客户端

    //以下导引free_list指向新分配的空间（取自内存池）
    *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->free_list_link = 0;
            break;
        }
        else{
            current_obj->free_list_link = next_obj;
        }
    }
    return result;
}

//内存池配置内存
//调用chunk_alloc()，尝试取得nobjs个区块作为free_list的新节点
//注意参数nobjs是pass by reference
char* Alloc::chunk_alloc(size_t size, int& nobjs){
    char* result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free; //内存池剩余内存

    if (bytes_left >= total_bytes){
        //内存池剩余空间完全满足需求量
        result = start_free;
        start_free += total_bytes;
        return (result);
    }
    else if (bytes_left >= size){
        //内存池剩余空间不能满足总的需求量，但足够供应大于等于1个的区块
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else{
        //内存池剩余空间连一个区块的大小都无法提供s
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        //以下试着让内存池的残余零头还要利用价值
        //首先寻找释放的free_list
        if (bytes_left > 0){
            obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);

            //调整free_list，将内存池中的剩余空间插入
            ((obj*)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*)start_free;
        }

        //配置heap空间，用来补充内存池
        start_free = (char*)malloc(bytes_to_get);
        if (start_free == 0){
            //heap空间不足，malloc失败
            int i;
            obj* volatile *my_free_list, *p;
            //以下搜寻适当的free_list
            //所谓适当是指“尚有未用区块，且区块够大”的free_list
            for (i = size; i <= MAX_BYTES; i += ALIGN){
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (p != 0){
                    *my_free_list = p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    //递归调用自己，为了修正nobjs
                    return (chunk_alloc(size, nobjs));
                }
            }
            end_free = 0;
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        //递归调用自己，为了修正nobjs
        return (chunk_alloc(size, nobjs));
    }
}

测试文件：main.cpp

#include"memorypool.h"
#include<vector>

int main(){

    Alloc pool;
    int* p = (int*)pool.allocate(sizeof(int)* 10);
    if (p == 0)cout << "allocate error." << endl;

    for (int i = 0; i < 10; i++)p[i] = i;
    for (int i = 0; i < 10; i++)cout << p[i] << " ";
    cout << endl;
    pool.deallocate(p, 40);

    system("pause");
    return 0;
}