C++内存管理学习笔记

当申请一块内存时，最终会使用malloc函数，这个函数申请到的内存会携带cookie信息而造成浪费，所以我们可以一次申请一大块的内存，共享cookie，再自己进行内存的分配。第一次写文章，尽量将注释写清楚，自己也在学习，有什么不对的别骂我，一起讨论。

代码如下

namespace per_class_allocator
{
	class Screen
	{
	public:
		//构造函数
		Screen(int x) :i(x) {};
		//提供接口
		int get() { return i; };
		//重载类内operator new() 和 operator delete() 实现内存管理
		void* operator new(size_t size);
		void operator delete(void* pdead, size_t size);
	private:
		int i;
	private:
		Screen* next;//增加一个指针
		//※※静态变量类内声明，类外定义赋初值
		//之所以定义为静态变量，我觉得是因为在分配内存的时候就要用到，这时对象还没有构造。
		static Screen* freeStore;//指向第一块空闲内存块的指针
		static const int screenChunk;//划分内存块的数量
	};
	Screen* Screen::freeStore = 0;//类外定义赋初值
	const int Screen::screenChunk = 24;
	//类外实现，operator new()的作用就是返回一块内存,由malloc实现，这里调用了new，本质上也是malloc
	void* Screen::operator new(size_t size)
	{
		//这里很重要，我们们一次性的申请一大块内存，然后分成块，并且用指针连着
		Screen* p;//一个指向Screen对象的指针，这是我们要返回的内存块的指针
		if (!freeStore)
		{
			//如果没有空闲内存块，进入到这里
			size_t chunk = screenChunk * size;//数量*一个对象的大小
			//连续申请一大块。
			freeStore = p = reinterpret_cast(new char[chunk]);
			//申请好了一大块内存，将其分开，并用指针串成链表
			for (; p != &freeStore[screenChunk - 1]; p++)
			{
				p->next = p + 1;//用链表穿起来
			}
			p->next = 0;
		}
		p = freeStore;
		freeStore = freeStore->next;
		return p;
	}
	void Screen::operator delete(void* pdead, size_t size)
	{
		//operator delete函数中虽然没有使用free，但是依然没有造成内存泄漏，
		//因为“释放“掉的这块内存还在我们的掌握中，并没有丢失
		//链表头插操作
		(static_cast(pdead))->next = freeStore;
		freeStore = static_cast(pdead);
	}
}

为了解决连接内存块的额外的指针next造成的浪费，使用类对象前四个字节来存放指针next。首先分析一下何时才会用到指针next：1、构造对象之前，用以连接内存块；2、析构对象之后，用以“回收”内存块。其余时间不需要next，这点内存就可以存放对象成员。所以指针和对象成员可以共用这四个字节以减少浪费。
代码如下：

namespace per_class_allocator_2
{
	class Airplane
	{
	public:
	//提供接口
		unsigned long getMiles() { return rep.miles; };
		char getType() { return rep.type; };
		void set(unsigned long m, char t)
		{
			rep.miles = m;
			rep.type = t;
		}
	public:
	//重载类内operator new()和operator delete()函数
		void* operator new(size_t size);
		void operator delete(void* pdead, size_t size);
	private:
		//将本身的成员集成在一个结构体
		struct  AirplaneRep{
			unsigned long miles;
			char type;
		};
	private:
	//用一个匿名的联合体
		union 
		{
			AirplaneRep rep;
			Airplane* next;
		};
	private:
	//同样定义静态成员
		static const int BLOCK_SIZE;//类外定义
		static Airplane* headOfFreeList;
	
	};
	const int Airplane::BLOCK_SIZE = 512;
	Airplane* Airplane::headOfFreeList = 0;

	void* Airplane::operator new(size_t size)
	{
		//先定义一个指向Airplane的指针，这个也是我们要返回的指针，这个指针指向可以使用的第一块内存
		Airplane* p = headOfFreeList;
		if (p)
		//若果p存在说明已经开辟好了内存池且有空位
		//那么直接让headOfFreeList指向下一块内存块
			headOfFreeList = headOfFreeList->next;
		else
		{
			//否则，申请一大块的内存，这里调用了全局的operator new（），会返回一个void*,再使用类型转换转换为Airplane*类型。
			Airplane* newBlock = static_cast(::operator new(BLOCK_SIZE * sizeof(Airplane)));
			//将申请好的内存分成BLOCK_SIZE大小，并用指针连接成一个单链表
			for (int i = 1; i < BLOCK_SIZE - 1; i++)
			{
				newBlock[i].next = &newBlock[i + 1];
			}
			newBlock[BLOCK_SIZE - 1].next = 0;//将最后一块内存置为nullptr
			//将headOfFreeList指向空闲的内存块，第一块内存块也就是newBlock[0]应当返回，所以headOfFreeList应当指向一下块
			headOfFreeList = &newBlock[1];
			p = &newBlock[0];
		}
		return p;
	}
	void operator delete(void* pdead, size_t size)
	{
		if (pdead == 0)
			return;
		if (size != sizeof(Airplane))
		{
			::operator delete(pdead);
			return;
		}
		//接下来就是正常的“回收”释放掉的内存块
		Airplane* acc = static_cast(pdead);
		acc->next = headOfFreeList;
		headOfFreeList = headOfFreeList->next;
	}
}

第二个版本虽然已经可以为自己定义的类进行内存管理，但是每一个类都要重载自己的类内operator new()和operator delete()函数，代码复用性不高，考虑将其封装为一个类，并且提供接口，这种思想已经接近标准库的alloctor实现思想，只需要稍加改良。代码如下：

namespace per_class_allocator_3
{
	class allocator
	{
	private:
		struct obj {
			struct obj* next;//还是使用嵌入式指针，只有一个成员，使用struct和union效果一样。
		};
	public:
		//提供接口
		//这里不能使用静态成员函数，否则无法调用非静态成员freeStore
		void* allcoate(size_t size);
		void deallcoate(void* pdead, size_t size);
	private:
		const int CHUNK = 5;
		obj* freeStore = 0;
	};
	void* allocator::allcoate(size_t size)
	{
		//这里面正常走分配内存的逻辑
		obj* p;
		if (!freeStore)
		{
			//没有空闲内存，分配一大块
			size_t chunk = CHUNK * size;
			freeStore = p = (obj*)malloc(chunk);//分配完毕
			//分割
			for (int i = 1; i < CHUNK; i++)
			{
				//为了适应不同的类的内存块大小的分割，后续会详细解释
				p->next = (obj*)((char*)p + size);
				p = p->next;	
			}
			p->next = 0;
		}
		p = freeStore;
		freeStore = p->next;
		return p;
	}
	void allocator::deallcoate(void* pdead, size_t  size)
	{
		static_cast(pdead)->next = freeStore;
		freeStore = (obj*)pdead;
	}
	//使用方法：不需要在类内写复杂的内存管理，直接调用接口
	class Text
	{
	public:
		static allocator My_alloc;//类外定义
		string str;
		long L;
		int I;
	public:
		//在类内还是要重载operator new()和operator delete()但是调用My_alloc的接口
		Text(const string& s, const long l, const int i) :str(s), L(l), I(i) {};
		static void* operator new(size_t size)
		{
			return My_alloc.allcoate(size);
		}
		static void operator delete(void* pdead, size_t size)
		{
			return My_alloc.deallcoate(pdead, size);
		}
	};
	allocator Text::My_alloc;
}

实现思路是对大小为8byte、16byte、24byte直到128byte（一共16种）的对象进行无cookie的内存分配，对于超过128byte的对象使用malloc分配内存。具体实现看代码，注释写的比较详细。

#include
namespace tiny_alloc
{
	//定义一些常量
	//size_t 是无符号整数，是任何对象可以达到的最大长度
	const size_t _ALIGN = 8;//标准规格，8比特为每次增长单位长度
	const size_t _MAX_BYTES = 128;//最大内存块
	const size_t _NFREELISTS = _MAX_BYTES / _ALIGN;//16个链表 从8byte -> 128byte
	class _default_alloc
	{
	private:
		static size_t ROUND_UP(size_t size)
		{
			//这个函数的作用是将传入的size调整为8的倍数
			//没有实现
		}
	private:
		//设置一个嵌入式指针
		union obj
		{
			union obj* free_list_link;
		};
		//使用struct也可以
		//若有多个成员，使用union，如果只有一个，使用struct也可以
	private:
		//方法都是静态的
		static obj* free_list[_NFREELISTS];//创建含有16个链表的数组
		static size_t FREELIST_INDEX(size_t bytes)
		{
			//根据对象大小，计算应该“哪条链表”中给他分配内存
			return (((bytes)+_ALIGN - 1) / _ALIGN - 1);
		}
		//内存的添加分为两步，1、申请内存块，存入战备池；2、将战备池的内存增加到内存链中
		static void* refill(size_t size);//填充,将已经申请到的内存充入链表中
		static char* chunk_alloc(size_t size,int &nojbs);//申请一大块内存，使用引用传递的原因是不一定能申请到足够数量的内存块，不够数量时，返回当前能申请的数量
		//提供的接口
		static void* allocate(size_t n)
		{
			obj** my_free_list;//用以保存选择哪条内存链表
			obj* result;//将要返回的指针
			if (n > (size_t)_MAX_BYTES)
			{
				//对象大小超过128，使用malloc分配
				result = (obj*)malloc(n);
				return result;
			}
			//1、先定位到哪一根链表
			my_free_list = free_list + FREELIST_INDEX(n);
			result = *my_free_list;
			if (result == 0)
			{
				//没有空闲内存，将战备池的内存充入链表中
				void* r = refill(ROUND_UP(n));//只需要传入对象的大小，具体大小不用输入
				return r;//将这个内存地址首地址传出即可
			}
				*my_free_list = result->free_list_link;
				return result;
		}
		static void deallocate(void* pdead, size_t size)
		{ 

			//除了检查大小以外，还要检查这块内存是不是由alloc这个系统得到的，
			//其他方式得到的内存也可以用这个方法回收，可能会造成灾难。
			//如果是malloc申请的就用free回收
			if (size > (size_t)_MAX_BYTES)
			{
			//这里可能有错误，但是思路就是使用malloc分配的就用free回收
				free(pdead);
			}
			//如果不是malloc分配的，还是使用指针头插法回收
			//先计算在那一条链表上
			obj** my_free_list = free_list + FREELIST_INDEX(size);
			((obj*)pdead)->free_list_link = *my_free_list;
			*my_free_list = (obj*)pdead; 
		}
		//定义指向战备池的首尾两端
		static char* start_free;
		static char* end_free;
		static size_t heap_size;//申请累计数
	};
	//静态成员定义
	_default_alloc::obj*  _default_alloc::free_list[_NFREELISTS]{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
	char* _default_alloc::start_free = 0;
	char* _default_alloc::end_free = 0;
	size_t _default_alloc::heap_size = 0;

//重点是下面这两个函数的实现
	void* _default_alloc::refill(size_t size)
	{
		//refill函数是填充内存到链表
		//传入的size已经被修正过，是8的倍数
		int nobjs = 20;//默认20个，可以随意更改，这个就是内存链表的长度
		//chunk_alloc函数帮助申请到内存
		char* chunk = chunk_alloc(size, nobjs);
		obj** my_free_list;//链表数组【索引】
		//这两个用于内存切割
		obj* current_obj;//当前要操作的
		obj* next_obj;//下一个要操作的
		int i;
		//这里为什么不写成nobjs == 1是因为害怕操作失误写成nobjs=1，这个不会报错。
		if (1 == nobjs) 
			return chunk;//如果只申请到一块，那么不需要再做处理，直接返回当前地址
		my_free_list = free_list + FREELIST_INDEX(size);//计算在第几个链表上进行填充
		//对申请到的一大块内存进行分割
		obj* result = (obj*)chunk;
		*my_free_list = next_obj = (obj*)(chunk + size);//因为申请机制的原因，使用+size的方法跳转到下一个。申请机制在chunk_alloc函数中讲。
		for (i = 1; ; i++)
		{
			//第一块给了result返回，直接从第二块开始链起
			current_obj = next_obj;
			next_obj = (obj*)((char*)current_obj + size);
			if (i == nobjs - 1)
			{
				//链接完了，当前要操作的内存块一下块为nullptr
				current_obj->free_list_link = 0;
				break;//退出for循环
			}
			else
			{
				current_obj->free_list_link = next_obj;
			}
		}
		return result;
	}
	//申请操作  重中之重
	char* _default_alloc::chunk_alloc(size_t size, int& nobjs)
	{
		char* result;//要返回的指针
		//首先计算我想要多大的内存
		size_t total_byte = size * (size_t)nobjs;
		//计算战备区还剩下多少内存
		size_t bytes_left = end_free - start_free;
		//1、第一种情况，战备池足够大
		if (bytes_left >= total_byte)
		{
			result = start_free;
			//降低水位
			start_free += total_byte;
			return result;
		}
		//2、第二种情况，战备池不够大,但是足够分配一个
		if (bytes_left >= size)
		{
			//首先更改需求，（这就是传入引用的原因）
			nobjs = bytes_left / size;//更新需求
			//重新计算需求
			total_byte = nobjs * size;
			result = start_free;
			//降低水位
			start_free += total_byte;
			return result;
		}
		//第三种情况，战备池不足了，需要重新分配，要处理两件事，1、残余的内存碎片要处理掉，2、申请新内存。
		if (bytes_left < size)
		{
		//申请机制：你想要大小为s的内存，会申请给你s*2+渐增量。渐增量 = 累计申请量/16 因为随着申请次数增多，你要是用的内存是跟着增加的。
			size_t bytes_to_get = 2 * total_byte + ROUND_UP(heap_size >> 4);//首先要申请的内存*2，一半用于分割为20块，一半用作战备池，其次根据经验，把已经申请的内存大小/16并且上提为8的倍数也作为战备池。
			//如果有碎片，先处理碎片问题
			if (bytes_left > 0)
			{
				//将该碎片链到大小合适的另一根链表上。
				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;
			}
			//处理完碎片开始申请
			start_free = (char*)malloc(bytes_to_get);
			//若是内存不够申请（可能性非常小）则向右边的内存链寻找空余的内存
			if (0 == start_free)
			{
				obj** my_free_list;
				obj* p;
				int i;
				//向右寻找，只能寻找一块，因为是链表连起来的，不确定是否连续
				for (i = size; i <= _MAX_BYTES; i += _ALIGN)
				{
					//先计算出第几个链表
					my_free_list = free_list + FREELIST_INDEX(size);
					p = *my_free_list;
					if (!p)
					{
					//还是将其充入战备池
						start_free = (char*)p;
						end_free = (char*)(p + size);
						//递归调用，只是用战备池的内存向链表中充
						return chunk_alloc(size, nobjs);
					}
				}
				//至此，向右的链表组中也没有可以分配的内存
				end_free = 0;
				//源码中还有一个一级分配器，用于处理这种情况，这里没有实现
			}
			//无论是直接申请，还是在靠右的链表中获取，或者使用一级分配器获取，至此申请成功。
			heap_size += bytes_to_get;//更新累积量
			end_free = start_free + bytes_to_get;//设置end_free
			//重点：现在战备池是有东西了，但是不知道够不够用，再次递归调用chunk_alloc函数
			return chunk_alloc(size, nobjs);
		}
	}
}