首页 > 代码库 > SGI空间分配器之第二级配置器剖析

SGI空间分配器之第二级配置器剖析

template<bool threads,int inst>class __default_alloc_template{private:    enum {__ALIGN=8};    enum {__MAX_BYTES=128;};    enum {__NFREELISTS=__MAX_BYTES/__ALIGN};        /*struct obj    {        struct obj* free_list_link;    };*/    //结构体和下面,在此处中是效果一致的。本模板采取此数据结构    //相对好处,不是很明白
 union obj    {        union obj* free_list_link;        char client_data[1];    };        //函数FREELIST_INDEX表示返回free_list[16]一个索引值    static size_t FREELIST_INDEX(size_t n)    {        return (((n)+__ALIGN-1)/__ALIGN-1);//返回对应的0-15的值。    }    //函数ROUND_UP出现,是为了对于空间大小是8,16,。。。128固定值,让n量化为其中某个值。    size_t ROUND_UP(size_t n)    {        //等效于return(((n-1)/__ALIGN+1)*__ALIGN);        return ((n+__ALIGN-1)&~(__ALIGN-1));    }    //函数chunk_alloc用于申请空间,想内存池    char* chunk_alloc(size_t n,size_t nobjs)    {        char * result;        size_t total_bytes=n*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>=n)        {//满足一个以上            result=start_free;            nobjs=bytes_left/n;//修正个数值            total_bytes=nobjs*n;            start_free+=total_bytes;            return result;        }        else        {//一个都满足不了了            if(bytes_left>0)            {//有内存;注意由于分配出来的都是8的倍数,则此时内存残余也是8的倍数                //收集残余内存                obj* volatile * my_free_list=free_list+FREELIST_INDEX(bytes_left);//适合残余bytes_left的空间收集                ((obj*)start_free)->free_list_link=*my_free_list;                 *my_free_list=(obj*)start_free;            }            //收集完本池中的残余空间后,则重新申请空间作为内存池。            //针对要求空间total_bytes,进行分配预留更多的,且考虑附加量,与已经申请了多少堆有关。            size_t bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4);            start_free=(char *)malloc(bytes_to_get);            if(start_free==0)            {//申请内存空间失败                //首先检测比分配空间更大的空间表是否有空闲内存。                            obj *volatile*my_free_list,*p;//注意此处*p是obj *p                for(i=n;i<=__MAX_BYTES;i+=__ALIGN)                {                    my_free_list=free_list+FREELIST_INDEX(i);                    p=*my_free_list;                    if(0!=p)                    {//表示i的空间大小有空闲,则将其空间从中删除,作为内存池                        *my_free_list=*my_free_list->free_list_link;                        start_free=(char*)p;                        end_free=(char*)p+i;                        chunk_alloc(n,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;            return chunk_alloc(n,nobjs);//已经分配到空间了,内存池重新注满水了,下一步就是类似前面的返回所需空间了        }    }    //函数refill重新分配固定空间个数    void* refill(size_t n)    {        //默认大小空间数是20;        int nobjs=20;        //向内存池中申请空间,以提供给客端空间申请要求        char *chunk=chunk_alloc(n,nobjs);//nobjs表示希望的个数,如果实际内存池不够,则会修改该值。        obj * result,*current_obj,*next_obj;                    obj* volatile *my_free_list;        if(nobjs==1) return(chunk);//此处注意,它表示申请不到20个空间,只能是一个,char*转为void*。                my_free_list=free_list+FREELIST_INDEX(n);//由于不止一个,则就需要修改空间链表指针。        result=(obj*)chunk;//char*转为obj*         next_obj=(obj*)(chunk+n);//char*转为obj*         *my_free_list=next_obj;//表示所指空间链表首地址        for(i=1;;i++)        {            current_obj=next_obj;            next_obj=(obj*)((char*)next_obj+n);//obj* 转为char*;char*转为obj*            if(nobjs-1==i)//表示分配了nobjs个但是有个被用了,故而就只有这么多个            {                current_obj->free_list_link=0;//最后一个设置为0;则当它被用了后,则原表中的指针只能值为0;                break;            }            else                current_obj->free_list_link=next_obj;        }        return result;    //obj*转为void*    }        static obj* volatile free_list[__NFREELISTS];    static char* end_free;    static char* start_free;    static size_t heap_size;public:    static void *allocate(size_t n)    {    //指针值,该指针指向一个obj*值,且是不可优化的,也就是free_list[16]值不可优化。        obj * volatile *my_free_list;    //分配空间结果位置---返回时其实质也就转为了void*指针类型了。被用时又转为相应的类型        obj * result;        if(n>(size_t)__MAX_BYTES)            return (malloc_alloc::allocate(n));                my_free_list=free_list+FREELIST_INDEX;//根据待分配空间大小给出指针所指free_list的值        //free_list数组所指是空间链表,链表如果没有空间则指向的是0值,否则是空间首地址。        result=*my_free_list;//所指空间处        if(0==result)        {            //需要申请空间配置扩展该固定字段空间。            void *p=refill(ROUND_UP(n));//表示分配后空间,返回一个被用,ROUND_UP是表示n上调其固定值。            return p;                }        //如果成功被分配出去了,则下面就得调整本链表空间。        *my_free_list=result->free_list_link;//只需要修改所指所指首地址,没有空间则指为0        return result;//obj*转为void*    }    static void deallocate(void *p ,size_t n)    {        if(n>__MAX_BYTES)            return (malloc_alloc::deallocate(p,n));        obj* volatile * my_free_list=free_list+FREELIST_INDEX;        ((obj*)p)->free_list_link=*my_free_list;        *my_free_list=(obj*)p;    }    static void *reallocate(void *p ,size_t old_sz,size_t new_sz)    {        void * result;        size_t copy_sz;        //对于老的内存,新的内存都大于128则交给一级处理        if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES)            return(realloc(p, new_sz));        //对于新旧内存上调后一致,则不需要重新分配空间        if (ROUND_UP(old_sz) == ROUND_UP(new_sz))            return(p);        //否则先利用分配空间,分出来        result = allocate(new_sz);        //复制其中空间内容        copy_sz = new_sz > old_sz? old_sz : new_sz;//取空间小的;这里有可能是全拷贝,有富裕空间;也有可能是截断拷贝        memcpy(result, p, copy_sz);//函数用于复制在#include <string.h>;C语言库中        //复制完后,进行收回原来的内存空间。        deallocate(p, old_sz);        return(result);    }};

SGI空间分配器之第二级配置器剖析