【STL】STL空间配置器

忘是亡心i 2022-07-14 13:29 172阅读 0赞

STL标准规格告诉我们，STL配置器定义于<memory>中，而SGI的<memory>中含有两个文件。

#include<stl_alloc.h> //内存空间的配置与释放
    #include<stl_construct.h> //对象内容的构造与析构

我们看到，STL的配置器allocator是将内存空间的配置与释放和对象的构造与析构这两部分操作分开处理的。分别定义与两个文件内，各自负责各自的功能。

除了这两个文件以外，<memory>中还定义了一些全局函数用来填充或复制大量数据。uninitalized\_copy、uninitialized\_fill、uninitialized\_fill\_n等。

由此我们可以画出配置器<memory>的框架。三部分相辅而成。

![20161211172539465][]

**stl\_construct.h**

stl\_construct.h中主要定义了两个基本函数。构造用construct()，析构用destroy()。这两个函数也被设计成 全局函数，符合STL的规范。

**stl\_alloc.h**

空间配置器的重点主要还是配置空间，本博文也主要堆stl\_alloc.h做出中点讲解。对象构造前的空间配置与对象析构后的空间释放都由<stl\_alloc.h>负责，SGI STL的主要设计思路如下：

*  向system heap要求空间（底层由malloc开辟空间）
 *  考虑多线程的问题
 *  考虑内存不足时应如何处理
 *  考虑内存碎片问题

stl\_alloc.h主要是由两级空间配置器组成。两级相互辅助工作，共同完成stl容器的空间分配工作。当所需要的空间大于128byte时，认为分配的内存较“大”，调用一级空间配置器\_\_malloc\_alloc\_template；当所需要的空间小于128byte时，认为分配的内存较“小”，为了降低malloc/free带来的开销负担，调用二极空间配置器\_\_default\_alloc\_template。

**优点**

这种做法有两个优点：

(1)小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。

(2)避免了内存碎片（外碎片）的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

**一级空间配置器\_\_malloc\_alloc\_template**

直观来说，一级空间配置器\_\_malloc\_alloc\_template在空间的分配与释放上是直接调用了malloc和free。在内存不足分配失败的处理机制上，它模拟了c++的set\_new\_handler()。

实现方法是：内存分配(malloc)失败时，会调用一个oom\_malloc函数来处理，函数内会调用“内存不足处理例程”，使系统回收一部分空间。然后再次malloc。若还是失败，则再次调用“内存不足处理例程”。。。不断循环直到“内存不足处理例程”未被设定或者开辟成功。当“内存不足处理例程”未被设定时 直接调用\_THROW\_BAD\_ALLOC, 丢出bad\_alloc异常信息**。**

**整体逻辑图**

**![20161211172826638][]**

**实现代码：**

/*
    一级空间配置器
    allocate()直接调用malloc
    dallocate()直接调用free
    模拟C++的set_new_handler处理内存不足的情况
    */
    #pragma once  
    #include<iostream>
    using namespace std;
    
    template<int inst>
    class MallocAllocTemplate
    {
    protected:
    	typedef void (*ALLOCATEHANDER)();
    	 static ALLOCATEHANDER __MallocAllocOomHandler;
    public:
    
    
    	//设置函数指针 __MallocAllocOomHandler的值
    	static ALLOCATEHANDER SetAllocHandler(void(*f)())
    	{
    		void(*old)() = __MallocAllocOomHandler;
    		__MallocAllocOomHandler = f;
    		return old;
    	}
    
    	//分配空间
    	static void* Allocate(size_t n)
    	{
    
    		__TRACE_DEBUG("调用一级空间配置器，分配%u个字节",n);
    		//开辟空间
    		//若开辟失败，则调用OOM_Malloc函数令系统回收空间
    		void *ret = malloc(n);
    		if (ret == NULL)
    		{
    			ret = OOM_Malloc(n);
    		}
    		return ret;
    	}
    
    
    	//释放空间
    	static void* Deallocate(void *ptr)
    	{
    		free(ptr);
    	}
    
    
    	//开辟空间失败后的处理函数
    	static void* OOM_Malloc(size_t n)
    	{
    		ALLOCATEHANDER MyAllocHandler;
    		void *ret;
    
    		//不断尝试释放，配置，再释放，再配置。。。
    		while (1)
    		{
    			//将系统回收空间的方法赋给MyAllocHandler
    			MyAllocHandler = __MallocAllocOomHandler;
    			if (MyAllocHandler == 0)
    			{
    				throw bad_alloc();
    			}
    			//调用方法回收空间
    			(*MyAllocHandler)();
    			//重新开辟
    			ret = malloc(n);
    			// 判断是否开辟成功，若成功：返回ret，若失败：继续循环开辟；
    			if (ret)
    			{
    				return ret;
    			}
    		}
    	}
    
    };
    
    
    template<int inst>
    typename MallocAllocTemplate<inst>::ALLOCATEHANDER
    MallocAllocTemplate<inst>::__MallocAllocOomHandler = 0;

**二级空间配置器\_\_default\_alloc\_template**

二级空间配置器\_\_default\_alloc\_template相对来说较为复杂，它只分配小于128字节的空间，我们可以认为它维护了一个内存池MemoryPool（一个大块内存），并维护了一个大小为16的自由链表FreeList的数据结构来管理这个大内存块。

**自由链表**

自由链表的实质是一个指针数组，数组有16个结点，分别代表的内存字节大小为：8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128。对应的下标是0~15，如图所示：

![20161211173130291][]

每个结点的内容均是指向一个内存对象的指针。我们一般将这个对象称为 **区块**，下面是区块的结构：

union obj {
            union obj * free_list_link;//指向下一结点的指针
            char client_data[1];    /* The client sees this.        *///目前这个成员没有意义
      };

**分配原则：我们每次向内存池索要一个区块时，内存池都会多给我们额外的区块，这样我们就可以将其中一个区块作为分配的空间返回，将额外多出的以链表的形式挂到指针数组对应的下标下。这样，当我们再次需要相同内存大小的区块时，就可以绕过内存池，直接去自由链表中去拿了。**

**自由链表的查找：**

仔细观察每个结点字节数大小可以发现，这些数字均是8的倍数。所以分配空间时也只能分配8的倍数大小的区块。那当我们需要3字节，14字节，9字节等任意一个不是8倍数的数要怎么办呢？

我们规定

1byte~8bytr      ---------------------->8byte

9byte~16byte   ---------------------->16byte

17byte~24byte ---------------------->24byte

。。。以此类推直到128字节。

STL同时规定了一种算法来计算这种8的倍数：

static size_t ROUND_UP(size_t bytes) {
            return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
      }

因为我们需要对自由链表进行操作，还需要求得对应的下标，

1byte~8bytr      ---------------------->0

9byte~16byte   ---------------------->1

17byte~24byte ---------------------->2

...

120byte~128byte ------------------->15

万能的STL又提供了一个方法：（感兴趣的可以研究下）

static  size_t FREELIST_INDEX(size_t bytes) {
            return (((bytes) + __ALIGN-1)/__ALIGN - 1);
      }

知道了这些我们就可以进行一次演示了：

![20161211173407624][]

**二级空间配置器的空间分配allocate**

在讲它的空间分配之前先说明几个它内部维护的几个元素：

static char *start_free;//指向内存池（MemoryPool）中可用内存的头部。
      static char *end_free;//指向内存池（MemoryPool）中可用内存的尾部。

![20161211173508312][]

static size_t heap_size;//每次向系统申请内存池的大小的累加和。

比如我第一次申请100字节内存用于内存池。heap\_size = 100;

第二次申请200字节, heap\_size = heap\_size + 200 = 300;

第三次申请300字节, heap\_size = heap\_size + 300 = 600;

...以此类推。

\_\_default\_alloc\_template的内存分配函数allocate实现也很简单，我们传入参数n（我们所需要的内存大小），它会判断n是否大于128，当大于128字节时，直接丢给一级空间配置器处理。

当小于128时：

①它会先求得n对应自由链表下标，去自由链表中查找是否有对应区块。若有，则分配并返回。

②若自由链表没有，它会调用refill函数，refill函数又会调用chunk\_alloc函数向内存池申请nobjs个（自定，STL为20个） 对应结点字节大小的区块。 **refill**可分为2种情况。

*  内存池内存足够分配size个内存块。1<=size<=nobjs.  
    将nobjs置成size （chunk\_alloc函数内实现）,从内存池中分出size个内存块，将其中一个内存块返回，剩余的以链式结构挂到对应自由链表结点下等待被分配使用。结束。
 *  内存池只能分1个内存块  
    直接将其返回。结束。

ChunkAlloc函数内部可分为三种情况，设内存池剩余字节大小为Bytes\_Left = start\_Free - end\_Free，我们所需要的内存字节数位 totalBytes= size\*nobjs，

1.  **Bytes\_Left >= totalBytes //可以分配nobjs\*size个字节空间**  
    分配，重置start\_Free的位置，返回，结束。
2.  **Bytes\_Left >= size && Byte\_Left < totalBytes//不能分配nobjs个，但至少能分配一个**  
    能分配多少就分配多少，将实际可分配的size大小区块的数量赋给nobjs（nobjs = Byte\_left/size）,重置start\_Free的位置，返回，结束。
3.  **Bytes\_Left < size//一个都分配不了**  
    ①先查看是否还有剩余的字节（Byte\_left是否大于0），将剩余字节挂到自由链表对应的位置上。Byte\_left>0，Byte\_left一定小于size。  
      
    ②内存池已无可用内存，向系统申请l  
    计算向系统申请内存的大小ByteToGet，尽量申请比所需要的大。将所需要的返回，将剩下多申请的放到内存池，以备后面再分配所用。一般申请大小为ByteToGet = totalBytes\*2+RUOND\_UP(heap\_size >>4)  
      
      **>若申请失败**  
      检查自由链表，查看是否还有可用的比size大的区块。  
              **>若有**，则将其放回内存池。重置start\_free和end\_free。然后**递归调用ChunkAlloc**，将大于size的区块编入内存     池，递归再次调用ChunkAlloc，满足至少分配1个的条件，一定分配成功。若没有，重新  
             **>若没有**，调用一级空间配置器。调用之前将end\_free置成空，调用一级空间配置器进行最后挣扎，一级空间配置器中有提醒操作系统释放内存的机制“内存不足处理机制”，若一级空间配置器开辟失败（“内存不足处理机制”没有被设置），则直接会抛出bad\_alloc异常。//这也是为什么在上面将end\_free置成空，一般来说当捕获到异常我们不会直接终止程序，而会再次尝试执行重复操作，所以当在bad\_alloc异常被捕获后，我们可能会再次调用ChunkAlloc进行空间分配，若不将end\_free置成空，当再次计算Bytes\_left时，start\_free因为空间分配失败而是NULL,end\_free是一个极大的值，这样算出来的Bytes\_left就特别大，造成不可预知的错误。                   
      
      **>若申请成功|**  
      重置Start\_Free和End\_Free的位置，修改Heap\_size的置。**递归调用ChunkAlloc**。

**整体逻辑图**

**![20161211173720954][]**

**实现代码：**

#define _CRT_SECURE_NO_WARNINGS 1
    
    #pragma once
    
    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdarg.h>
    using namespace std;
    
    #include"MallocAllocTemplate.h"//包含一级空间配置器的头文件
    
    template<bool threads,int inst>
    class DefaultAllocTemplate
    {
    protected:
    	enum{_ALIGN = 8};
    	enum{_MAX_BYTES = 128};
    	enum{_NFREELISTS = _MAX_BYTES/_ALIGN};
    
    	//自由链表下挂的结点的类型
    	union obj
    	{
    		obj* FreeListLink;//指向下一个结点内存块的指针
    		char ClientData[1];
    	};
    
    	static obj* FreeList[_NFREELISTS];
    
    
    	//将n上升到8的倍数
    	static size_t ROUND_UP(size_t n)
    	{
    		return((n) + _ALIGN - 1)& ~(_ALIGN - 1);
    	}
    
    	//计算Freelist中的下标
    	static size_t _FREELIST_INDEX(size_t n)
    	{
    		return((n + _ALIGN - 1) / _ALIGN - 1);
    	}
    	//指向内存池可用空间的头
    	static char* Start_Free;
    	//指向内存池可用空间的尾o
    	static char* End_Free;
    	//向堆申请空间时所用 Chunk_Malloc
    	static size_t Heap_Size;
    public:
    	//分配空间
    	static void* Allocate(size_t n)
    	{
    
    		//若申请的空间大于128字节，调用一级空间配置器
    		if (n > (size_t)_MAX_BYTES)
    		{
    			__TRACE_DEBUG("大于128字节，调用一级空间配置器，分配%d个字节",n);
    			return(MallocAllocTemplate<inst>::Allocate(n));
    		}
    
    		__TRACE_DEBUG("小于128字节，调用二级空间配置器，先去自由链表中查找:")
    		obj** MyFreeList;//自由链表
    		obj* result;//返回值
    		
    		//_FREELIST_INDEX利用n计算下标
    		//MyFreeList找到相应大小内存块在自由链表中位置
    		MyFreeList = FreeList + _FREELIST_INDEX(n);
    		result = *MyFreeList;//将第一个内存块给result
    
    		//若分配失败，即自由链表中没有相应内存块
    		//调用Refill函数向内存池申请。
    		if (result == NULL)
    		{
    			
    			void* r = Refill(ROUND_UP(n));//ROUND_UP将n上升到8的倍数
    			return r;
    		}
    
    		__TRACE_DEBUG("自由链表中存在%u大小的区块，分配，返回，结束", n);
    		//令自由链表中指针指向下一个内存块
    		*MyFreeList = result->FreeListLink;
    		return result;
    
    	}
    	//释放空间
    	static void Deallocate(void* p, size_t n)
    	{
    		obj** MyFreeList;
    		obj* rb = (obj*)p;
    
    		if (n > _MAX_BYTES)
    		{
    			return MallocAllocTemplate<inst>::Deallocate(p, n);
    		}
    
    		MyFreeList = FreeList + _FREELIST_INDEX(n);
    		rb->FreeListLink = *MyFreeList;
    		MyFreeList = rb;
    	}
    
    	//向内存池申请空间
    	static void* Refill(size_t n)
    	{
    		__TRACE_DEBUG("自由链表没有所需要区块，调用Refill，向内存池申请");
    		int nobjs = 20;// 标准值：开辟20个内存块
    
    		char* chunk = NULL;
    
    
    		//如果内存池不足以开辟nobjs个内存块就会修改nobjs的值。
    		//内存池实际能开辟多少个大小为size的内存块就将nobjs的值设为多少
    		chunk = ChunkAlloc(n, nobjs);//向内存池申请内存
    
    		obj**MyFreeList;//自由链表
    		obj* cur_obj = NULL;//指向当前内存块的指针
    		obj* next_obj = NULL;//指向下一个内存块的指针
    		obj* result = NULL;//返回值
    
    
    		//若nbjs = 1，即内存池只剩下一个size大小的内存
    		//将其返回
    		if (nobjs == 1)
    		{
    			__TRACE_DEBUG("内存池只足以分配1个%u字节大小的区块，将其返回，程序结束", n);
    			return (obj*)chunk;
    		}
    
    
    
    		__TRACE_DEBUG("内存池分配了%d个的区块，将其中一个返回，剩下的%d块挂到自由链表上", nobjs, nobjs - 1);
    		//若nobjs>1，即内存池还有多个size大小的内存。
    		//将第一个返回，将剩下的链到自由链表上
    		
    		//准备自由链表，设置自由链表位置（下标）
    		MyFreeList = FreeList + _FREELIST_INDEX(n);
    
    		// 将第一个置成返回值
    		result = (obj*)chunk;
    
    		//  读取“下一块”空间
    		next_obj = (obj*)(chunk + n);
    
    		//  将自由链表指向“下一块”空间
    		*MyFreeList = next_obj;
    		
    		//再次读取下一块空间
    		next_obj = (obj*)((char*)next_obj + n);
    
    		
    	    //将剩下的链上
    		for (int i = 1; i < nobjs; i++)
    		{
    			cur_obj = next_obj;
    			if (i == nobjs - 1)
    			{
    				cur_obj->FreeListLink = NULL;
    				break;
    			}	
    			next_obj = (obj*)((char*)next_obj + n);
    			cur_obj->FreeListLink = next_obj;
    		}
    		
    		return result;
    
    	}
    
    	//内存池分配
    	static char* ChunkAlloc(size_t size, int &nobjs)
    	{
    		obj**MyFreeList;
    		char* ret = NULL;
    		size_t totalBytes = nobjs * size;
    		__TRACE_DEBUG("调用ChunkAlloc函数向内存池申请区块：%u个%d，共%u字节", nobjs, size, totalBytes);
    
    		size_t Bytes_left = End_Free - Start_Free;
    
    		if (Bytes_left >= totalBytes)
    		{
    			__TRACE_DEBUG("内存池内存足够，分配了：%u个%d，共%u字节", nobjs, size, totalBytes);
    			ret = Start_Free;
    			Start_Free += totalBytes;
    			return ret;
    		}
    		else if (Bytes_left >= size)
    		{
    			nobjs = Bytes_left / size;
    			//注意修改totalBytes，剩下的字节可能不足以开辟整数个size大小的区块
    			//可能有剩余
    			totalBytes = nobjs * size;
    			__TRACE_DEBUG("内存池内存不足，但至少可以分配1个，实际可分配:%d个%u，共%u字节", nobjs, size, totalBytes);
    			ret = Start_Free;
    			Start_Free += totalBytes;
    			return ret;
    		}
    		else
    		{
    			__TRACE_DEBUG("内存池干涸，连1个%u个字节的区块都无法分配",size);
    			//先查看内存池是否还有剩余内存，将剩余内存挂到自由链表上
    			if (Bytes_left > 0)
    			{
    				__TRACE_DEBUG("内存池剩余%u个字节，将其挂到自由链表上，防止浪费", Bytes_left);
    				MyFreeList = FreeList + _FREELIST_INDEX(Bytes_left);
    
    				((obj*)Start_Free)->FreeListLink = *MyFreeList;
    				*MyFreeList = (obj*)Start_Free;
    				Start_Free += Bytes_left;
    			}
    
    			//用malloc向系统申请内存
    			//将要申请的内存的大小上升至8的倍数
    			//多申请，一部分分配出去，一部分存入内存池
    
    			size_t BytesToGet = totalBytes * 2 + ROUND_UP(Heap_Size >> 4);
    
    			__TRACE_DEBUG("调用malloc，向系统申请%u个字节内存", BytesToGet);
    			Start_Free = (char*)malloc(BytesToGet);//malloc返回值为void*
    
    			//若malloc分配失败
    			if (Start_Free == NULL)
    		    {
    				__TRACE_DEBUG("向系统申请失败，去自由链表查找是否有比&u大的可用区块", size);
    				//先遍历自由链表查找是否有比size大的区块
    				for (size_t i = size; i < _MAX_BYTES; i += _ALIGN)
    				{
    					MyFreeList = FreeList + _FREELIST_INDEX(i);
    					obj* p = *MyFreeList;
    					if (p != NULL)
    					{
    						__TRACE_DEBUG("发现自由链表中有%u字节的可用区块，重置Start,End,递归调用ChunkAlloc", i);
    						Start_Free = (char*)p;
    						End_Free = Start_Free + i;
    						//将大于size的区块编入内存池，递归再次调用ChunkAlloc，满足至少分配1个的条件
    						//一定分配成功
    						return ChunkAlloc(size, nobjs);
    					}
    
    				}
    
    				__TRACE_DEBUG("自由链表中没有可用区块，将End置空，调用一级空间配置器进行最后挣扎");
    				End_Free = 0;//
    		        //调用一级空间配置器进行最后挣扎
    				//一级空间配置器中有提醒操作系统释放内存的机制“内存不足处理机制”
    				//若一级空间配置器开辟失败（“内存不足处理机制”没有被设置），则直接会抛出bad_alloc异常
    				//这也是为什么在上面将End_Free置成空，
    				//一般来说当捕获到异常我们不会直接终止程序，而会再次尝试执行重复操作
    				//所以当在bad_alloc异常被捕获后，我们可能会再次调用ChunkAlloc进行空间分配
    				//若不将End_Free置成空
    				//当再次计算Bytes_left时，Start_Free因为空间分配失败而是NULL,End_Free是一个极大的值
    				//这样算出来的Bytes_left就特别大，造成不可预知的错误。
    				Start_Free = (char*)MallocAllocTemplate<inst>::Allocate(BytesToGet);
    			}
    
    
    			__TRACE_DEBUG("malloc分配成功，重置Start，End，递归调用ChunkAlloc");
    			End_Free = Start_Free + BytesToGet;
    			Heap_Size += BytesToGet;
    			return ChunkAlloc(size, nobjs);
    		    
    		}
    
    		//内存池足以分配size*nobjs个字节的空间
    	    //内存池不足size*nobjs个字节，但可以分配1个以上size个字节的空间
    		//内存池不足以分配1个size
    	}
    
    };
    
    //将自由链表置成空
    template<bool threads,int inst>
    typename DefaultAllocTemplate<threads, inst>::obj*
    DefaultAllocTemplate<threads, inst>::FreeList[_NFREELISTS] = { 0 };
    
    template<bool threads,int inst>
    char* DefaultAllocTemplate<threads, inst>::Start_Free = 0;
    template<bool threads, int inst>
    char* DefaultAllocTemplate<threads, inst>::End_Free = 0;
    template<bool threads, int inst>
    size_t DefaultAllocTemplate<threads, inst>::Heap_Size = 0;

**小结：**

STL中的内存分配器实际上是基于空闲列表(free list)的分配策略，最主要的特点是通过组织16个空闲列表，对小对象的分配做了优化。  
1）小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。  
2）避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。

3）尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域，

但是，这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的，比如：

stl::vector<int> array;

array是知道它需要分配的对象大小为sizeof(int)。一个通用的内存分配器是不需要知道待释放内存的大小的，类似于free(p)。

[20161211172539465]: /images/20220714/534b759a09b24cbf8b531f9c64a818f1.png
[20161211172826638]: /images/20220714/50015a9904634cb6896e9b2e4e84a0e2.png
[20161211173130291]: /images/20220714/630cc4f9b1304ef2880093d5e6234e46.png
[20161211173407624]: /images/20220714/0eabd5d5659e4a46aae29ce366303b45.png
[20161211173508312]: /images/20220714/75da979a45af4c8c98a5cf0c617aa01b.png
[20161211173720954]: /images/20220714/e2b31c21481c463a9325c7e2b07e1a49.png