【tcmalloc】（二）整体设计和thread cache（申请）

一.高并发内存池整体框架设计

内存池需要考虑以下几方面的问题。
1. 性能问题。
2. 多线程环境下，锁竞争问题。
3. 内存碎片问题（外碎片（内存不连续无法使用），内碎片（因为对齐规则的浪费））

malloc 一进入多线程就加锁，tcmalloc有可能不用加锁。??

1.thread cache：线程缓存是每个线程独有的，用于小于256KB的内存的分配，线程从这里申请内
存不需要加锁，每个线程独享一个cache，这也就是这个并发线程池高效的地方。
2. central cache：中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对
象。central cache合适的时机回收thread cache中的对象，避免一个线程占用了太多的内存，而
其他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存
在竞争的，所以从这里取内存对象是需要加锁，首先这里用的是桶锁，其次只有thread cache的
没有内存对象时才会找central cache，所以这里竞争不会很激烈。
3. page cache：页缓存是在central cache缓存上面的一层缓存，存储的内存是以页为单位存储及分配的，central cache没有内存对象时，从page cache分配出一定数量的page，并切割成定长大小的小块内存，分配给central cache。当一个span的几个跨度页的对象都回收以后，page cache
会回收central cache满足条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片
的问题

二.threadcache 框架设计

?线程独有的内存池需要解决小于256kb的内存分配问题，我们可以试图利用定长内存池的自由链表，因为自由的申请释放都是o(1）的。（头插头删）但是因为定长内存池的自由链表只能申请同样的内存大小，我们这里会面临不同内存大小的申请情况【1～256】。虽然可以通过创建多个不同大小的自由链表解决这个问题，但这这意味着，需要创建256×1024个不同大小的自由链表。从1字节开始到256×1024字节。

所以我们采取桶结构处理这个问题。将内存划分为一个一个小区间，每个桶对应一个区间，每个桶节点下挂当前区间大小的自由链表。当申请的内存处于当前区间的时候都可以由当前桶的自由链表分配内存，这会导致有时候会产生内存内碎片（需要通过区间划分的规则调整让内存碎片最小）

三.实现细节

//线程缓冲区申请内存
void* ThreadCache::Allocate(size_t size)
{
	assert(size<=MAX_BYTES);
	//计算出对齐后申请内存的大小和桶下标
	size_t alignsize = SizeRules::ApplicationSize(size);	//（CentralCache要用）
	size_t index = SizeRules::Index(size);
	
	//检查哈希桶对应下标是否含有自由链表
	if (!_freelists[index].Empty())	//先用还回来的
	{
		//弹出内存块
		return _freelists[index].Pop();
	}
	else//没有了再找新的
	{
		return FetchFromCentralCache(index, alignsize);
	}
}
//线程缓冲区归还内存 
void* ThreadCache::Deallocate(void* obj, size_t size)
{
	assert(obj);
	assert(size <= MAX_BYTES);

	size_t index = SizeRules::Index(size);  //寻找还回来的内存块可以插入的位置
	_freelists[index].Push(obj);  //插入得到的内存块

	//当换回来的内存块超过一定值的时候，统一还给span内存块（central catche）
	//这里用一次批量申请的上限作为阀值
	if (_freelists[index].MemSize() >= _freelists[index].MaxSize())		//不一定memsize从0开始，_freelist挂的是没使用的内存若申请多了没使用memsize就不是0
	{
		//合并自由链表的小内存块并统一返还给centralcache
		ListTooLong(_freelists[index], size);
	}
	return obj;
}

四.无锁问题

采用TLS线程本地存储，每个线程独享自己的全局变量，这样就可以避免用锁?