STL — 浅析一级空间配置器

约定不等于承诺〃 2022-06-04 09:39 262阅读 0赞

# 浅析一级空间配置器 #

template < class T, class Alloc = allocator<T> >
    
    class vector;

上面是我们熟悉不能再熟悉的vector的声明式，我们以前也曾经尝试实现过vector，但是我们实现当中只有一个class T. 但是我们拉出

来 www.cplusplus.com当中声明，我们突然发现 居然有两个模板参数？ 然后我发现几乎所有的容器都会比平时多一个模板参数，

list,map,set等等他 们的后面都惊人的相似，有一个Alloc的模板 参数，那么这个Alloc是什么东西？ 其实它就是空间配置器，一个隐藏

在 所有容器背后的 大BOSS . 以STL的运用角度而言，空间配置器是最不需要介绍到东西. 因为它总是在暗中观察. 它总是隐藏在一切组件

的背 后，默默的工作，默默地付出自己的 劳动！ 所以我们不容许这么一个默默付出的人，却不为人知！ 所以我要写一篇博客来赞美他~

他其 实是一切容器能够高效运行并且节约空间的支柱， 我们在学习STL的 时候不先掌握空间配置器的原理，难免在阅读其他STL组件的实

现 的 时候处处遇到拦路石.

其实我们发现开辟空间使用new和delete还挺好用的啊. 为什么需要空间配置器？？? 这篇博客就是比较的偏重于一级空间配置器的介绍，

所以我们来 聊 一聊一级空间配置器的好处. 我们知道的malloc和new的区别之一有malloc开辟内存失败后会返回0而new开辟内存失败后会

抛异常. 一级空间配置器 就是 更大的程度来合理运用空间. 它的内部设计实际就是为了压榨剩余的内存，达到内存的高效运用. 所以一

级 空间配置器内部其实就是malloc和free 的封装，然后尽量的开辟出你想要的内存空间，就算系统内部的剩余内存空间小于你所申请的

内 存空间，它都会努力尝试开辟出来.

/*__malloc_alloc_template 就是第一级配置器*/  
    typedef __malloc_alloc_template<0> malloc_alloc;      
    typedef malloc_alloc alloc;

这是源代码当中一级空间配置器的声明式. 源代码当中一级空间配置重要的函数如下: allocate(开辟空间)，reallocate(开辟空

间)，deallocate(释 放空间). 我们先来看看它的alloacte以及相关函数的实现：

#define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)  
      
    static void* allocate(size_t __n)  
    {  
        void* __result = malloc(__n);      //调用malloc()分配内存，向 system heap 要求空间  
        if (0 == __result) __result = _S_oom_malloc(__n);     //malloc分配失败，调用_S_oom_malloc()  
        return __result;                                      
    }  
      
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG  
    template <int __inst>  
    void(*__malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;  
    #endif                       
    //内存不足处理例程，初值为0，待用户自定义，考虑内存不足时的应变措施。  
      
    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;  
            /*由于初值设定为0，如果用户没有自定义相应的内存不足处理例程，那么还是抛出异常*/  
            if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }    
            (*__my_malloc_handler)();          //用户有自定义(释放内存)，则进入相应的处理程序  
            __result = malloc(__n);              
            if (__result) return(__result);  
        }  
        //不断的尝试释放和配置是因为用户不知道还需要释放多少内存来满足分配需求，只能逐步的释放配置  
    }

根据注释很容易看懂代码往下走，唯一有一点点难度的地方就是那个死循环的地方，我们来着重看一下这个循环的内容:(敲敲黑板 重点

！![微笑][smile.gif]) 我们看到的for的那个循环并非死循环，我们看到的是\_malloc\_alloc\_oom\_handler初始值为0，然后如果用户有相应的内存不足

处理 函数时，下面的 \_my\_malloc\_handler就不会为0. 反之如果没有相应的内存不足 函数 ，那么在下一个语句我们的系统会直接抛出异

常 . 所以这个看似为死循环的循环

它有两个退出条件: 1.在反复使用用户定义了的释放内存函数后，我们成功的分配了指定大小的内存，返回指向该内存区域的首地址.

2.我们用户没有 定义相应的处理内存不足 函数 ,然后在if(0 == \_\_my\_malloc\_handler)这个if语句里面抛出异常. 其实我觉得这里还

是 会有一点点的问题，并不是 有用 户定义的处理内存不足函数 就可以一直反复的调用它，不断的释放出空间. 举一个极端的例子， 如

果用户定义的方法已经开辟不出来空间了，那么这个 时候系统是真的一点点内存空间都挤不出来了，那么这个 程序 就会变成 死循环.

所以我觉得用户自定义函数当中一定要有防范这种情况的东西. 比如 在函数里面判断一下本次函数有没有运行清理出来了空间，如果

有就进行循环调用. 如果没有清理出空间，就直接抛异常吧。系统已经山穷水尽了. 接下啦看一个跟allocate非常相似的函数

reallocate(). 我就直接粘贴代码了，你懂allocate就一定会懂reallocate：

static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)  
    {  
        void* __result = realloc(__p, __new_sz);  
        if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);  
        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);  
        }  
    }

最后是我们的deallocate，它的内部实现简单的出乎你的所料，单纯的封装一个free而已:

static void deallocate(void* __p, size_t /* __n */)  
    {  
        free(__p);        //第一级配置器直接使用free()  
    }

我们的一级空间配置器以malloc(),free(),realloc()等C函数执行实际的内存配置，释放，重配置的操作. 因为SGI不能直接使用C++的

set\_new\_handler()，我们必须仿真出来一个set\_malloc\_handler()来. 如果对set\_new\_handler不够了解可以去看看我

的这个博客:  set\_new\_handler

/*该函数接收一个返回值为空，参数为空的函数指针作为参数，最后返回一个返回值和参数均为空的函数指针*/  
    static void (* __set_malloc_handler(void (*__f)()))()     
    {  
        void (* __old)() = __malloc_alloc_oom_handler;       //保存原有处理例程  
        __malloc_alloc_oom_handler = __f;                    //重新指定异常处理例程  
        return(__old);  
    }

这个函数就是为了我们的用户自定义处理内存不足函数准备的，他重新指定了内存分配异常处理函数，并返回来原有的内存分配处理

函数，也就是设置 了新的处理函数也保存并返回了旧的处理函数.具体为什么要返回旧的处理函数，是将它保存起来方便以后又想使用

旧的处理函数的时候，更方便. 所以我们现在看看这整个一级配置器的过程: SGI一级配置器的allocate()和reallocate()都是在调 用

malloc()和realloc()不成功后，改调用 \_s\_oom\_malloc()和\_s\_omm\_realloc().后两者都有内循环，不断地重复调用用户自定处理内存

不足函数，希望在某次调用结束之后，可以获得我们申请 大小的内存，如果用户自定义处理内存不足函数未被用户定义，

\_s\_oom\_malloc()和\_s\_oom\_realloc()变回调用\_THROW\_BAN\_ALLOC，丢出bad\_alloc异常 信息，而且使用exit(1)退出程序.我们可以看

出 来这里释放空间是需要你自己给出方法来实现的，SGI做的只是给你一个一级空间配置器的框架. 既然我们懂得了它的构造框架那

么我们自己来实现一下我们自己的一级空间配置器:

#include<iostream>
    #include<Windows.h>
    
    using namespace std;
    
    //一级空间配置器
    #define _THROW_BAN_ALLOC 0
    
    template<int inst>
    class __MallocAllocTemplate
    {
    public:
    	static void* Allocate(size_t n)
    	{
    		void* result = malloc(n);
    		if (0 == result) result = __Oom_Malloc(n);
    
    		return result;
    	}
    
    	static void Deallocate(void* p)
    	{
    		free(p);
    	}
    	static void* Reallocate(void* p,size_t new_size)
    	{
    		void* result = realloc(p,new_size);
    		if (0 == result) result = __Oom_Realloc(p,new_size);
    
    		return result;
    	}
    
    	static void(*Set_Malloc_Handler(void(*f)()))()
    	{
    		void(*old)() = __Malloc_Alloc_Oom_Handler;
    		__Malloc_Alloc_Oom_Handler = f;
    		return(old);
    	}
    
    private:
    	static void(*__Malloc_Alloc_Oom_Handler)();
    
    	static void *__Oom_Malloc(size_t n)
    	{
    		void(*My_Malloc_Handler)();
    		void* result;
    
    		for (;;) 
    		{
    			My_Malloc_Handler = __Malloc_Alloc_Oom_Handler; //用户自定义处理函数地使用
    			if (My_Malloc_Handler == 0) 
    				throw _THROW_BAN_ALLOC;
    			(*My_Malloc_Handler)(); //调用处理函数释放内存;
    			result = malloc(n); //再次开辟内存
    			if (result)
    				return result;
    		}
    	}
    
    
    	static void *__Oom_Realloc(void *p,size_t n)
    	{
    		void(*My_Malloc_Handler)();
    		void* result;
    
    		for (;;)
    		{
    			My_Malloc_Handler = __Malloc_Alloc_Oom_Handler; //用户自定义处理函数地使用
    			if (My_Malloc_Handler == 0 )
    				throw _THROW_BAN_ALLOC;
    			(*My_Malloc_Handler)(); //调用处理函数释放内存;
    			result = realloc(p,n); //再次开辟内存
    			if (result)
    				return result;
    		}
    	}
    };
    
    template<int inst>
    void(*__MallocAllocTemplate<inst>::__Malloc_Alloc_Oom_Handler)() = 0; //默认为0
    
    typedef __MallocAllocTemplate<0> malloc_alloc;

我们尝试调用一下，这个一级空间配置器：

void Test()
    {
    	
    
    	int* p = (int*)malloc_alloc::Allocate(sizeof(int)* 10);
    
    	for (size_t i = 0; i < 10; ++i)
    	{
    		p[i] = i;
    	}
    
    	p = (int*)malloc_alloc::Reallocate(p, sizeof(int)* 20);
    	for (int i = 10; i < 20; ++i)
    	{
    		p[i] = i * 3;
    	}
    
    	for (int i = 0; i < 20; ++i)
    	{
    		cout << p[i] << " ";
    	}
    
    	malloc_alloc::Deallocate(p);
    
    	system("pause");
    }

运行结果:

![20171211134051468][]

运行结果很符合我们的要求，不过我们这个是直接开辟出来的空间，并没有走那个\_\_Oom\_Malloc和\_\_Oom\_Realloc函数，为了让程序跑起

来我们 定义一 个假的用户自定义 清理 空间函数吧，因为我们只需要了解一级空间配置器的运行过程，所以呢这个函数我就只让他输出一

个cout语句就好了. 现 在我们 开始运行，大家还记得我刚刚说过的如果用户自定义清理函数并没有清理出空间那么就应该让它立即抛出

一个异常因为系统内存已经山穷水尽了. 如果 不抛出一个异常就是死循环了. 那我们模拟一下这个场景：

template<int inst>
    void(*__MallocAllocTemplate<inst>::__Malloc_Alloc_Oom_Handler)() = 0; //默认为0
    
    typedef __MallocAllocTemplate<0> malloc_alloc;
    
    
    void DoFreeAlloc()
    {
    	for (int i = 0;; ++i)
    	{
    		cout << "我正在拼命地释放空间\n" << endl;
    	}
    }
    
    
    void Test()
    {
    	malloc_alloc::Set_Malloc_Handler(DoFreeAlloc);
    	
    	int* p = (int*)malloc_alloc::Allocate(sizeof(int*)* 1000000000);
    
    	malloc_alloc::Deallocate(p);
    
    	system("pause");
    }

这里我故意开辟一个很大的空间，让一级空间配置器调用\_\_Oom\_Malloc和\_\_Oom\_Realloc函数 ，然后这个自定义清理空间函数单纯输出

一句话并且没 有 清理出来空间，这就是模拟自定义清理空间函数无法再继续清理出空间的情况，我们来看一 看运行的结果：

![20171211135646838][]

不出我们所料果然变成了一个死循环，所以呢！ 我们需要在用户自定义清理空间函数中加上一个判断条件如果它本次没有清理出空间

，那么就 抛出异 常.这样是我自己的一点想法，如果那里有问题还希望大家一起来指出并讨论. 好了一级空间配置器就说到这里啦.

我找一张图帮大家理解：

![20180218205500626][]

# 一级空间配置器的缺陷 #

最后最后我丢一个问题： 如果你频繁的内存当中开辟出来不连续的小块内存会导致什么样的后果呢？？ 我们举个例子把堆得内存分

为8个部分， 如下图所示:

![20171211141430051][]

那么该如果解决这个问题呢？？ 这个就是我们二级空间配置器该出手的时候了，详情请听下回分解！

[smile.gif]: /images/20220604/9f459046e58145ed9a5e549630fe44f3.png
[20171211134051468]: /images/20220604/527c1105417e4da384f42cc11125b20c.png
[20171211135646838]: /images/20220604/85eea2624ed04cefa5ca28b008bf12b8.png
[20180218205500626]: /images/20220604/a653aafd5bfd4b47a3485b06b007b8c0.png
[20171211141430051]: /images/20220604/c8f8de580b41408f8eecd78c2b500abb.png