# concurrent_memory_pool

**Repository Path**: yuheng_li/concurrent_memory_pool

## Basic Information

- **Project Name**: concurrent_memory_pool
- **Description**: c++高并发内存池设计与实现
- **Primary Language**: Unknown
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2023-01-27
- **Last Updated**: 2025-02-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# ConcurrentMemoryPool

# 1.项目架构

项目设计分为三层结构：
![在这里插入图片描述](https://gitee.com/caoguangjing/concurrent_memory_pool/raw/master/memory.png)

- 第一层是Thread Cache，线程缓存是每个线程独有的，在这里设计的是用于小于64k的内存分配，线程在这里申请不需要加锁，每一个线程都有自己独立的cache，这也就是这个项目并发高效的地方。

- 第二层是Central Cache，在这里是所有线程共享的，它起着承上启下的作用，Thread Cache是按需要从Central Cache中获取对象，它就要起着平衡多个线程按需调度的作用，既可以将内存对象分配给Thread Cache来的每个线程，又可以将线程归还回来的内存进行管理。Central Cache是存在竞争的，所以在这里取内存对象的时候是需要加锁的，但是锁的力度可以控制得很小。

- 第三层是Page Cache，存储的是以页为单位存储及分配的，Central Cache没有内存对象(Span)时，从Page cache分配出一定数量的Page，并切割成定长大小的小块内存，分配给Central Cache。Page Cache会回收Central Cache满足条件的Span(使用计数为0)对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。

  其中span结构如下：

  ```
  //Span是一个跨度，既可以分配内存出去，也是负责将内存回收回来到PageCache合并
  //是一链式结构，定义为结构体就行，避免需要很多的友元
  struct Span
  {
  	PageID _pageid = 0;//页号
  	size_t _npage = 0;//页数
  
  	Span* _prev = nullptr;
  	Span* _next = nullptr;
  
  	void* _list = nullptr;//链接对象的自由链表，后面有对象就不为空，没有对象就是空
  	size_t _objsize = 0;//对象的大小
  
  	size_t _usecount = 0;//对象使用计数,
  };
  ```

  

# 2.对齐大小的设计

```
	// 控制在12%左右的内碎片浪费
	// [1,128]				8byte对齐 freelist[0,16)
	// [129,1024]			16byte对齐 freelist[16,72)
	// [1025,8*1024]		128byte对齐 freelist[72,128)
	// [8*1024+1,64*1024]	1024byte对齐 freelist[128,184)
```

# 3.基数树设计

​	利用**基数树(radix tree)**完成内存和各级内存池之间的映射关系；

### 	1.为什么需要基数树

​		申请内存是需要调用函数ConcurrentAlloc，输入申请内存的大小size;同时返回指针ptr;

​		释放内存时需要调用函数ConcurrentFree，输入指针ptr；

```C++
void* ConcurrentAlloc(size_t size);//申请内存
void ConcurrentFree(void* ptr)//释放内存
```

​		**此时会有一个问题，如何知道释放指针ptr所指向的内存大小？**

​		简单点的话直接使用哈希表映射，**key为：指针ptr，value为：内存大小size**；

​		这当然可以，不过由于我们在管理内存池时，通常是一页一页内存进行管理的，比如32位平台下，将一页内存化分为4K,为每一页都会有一个页号，指针ptr和页号都是具有一一对应关系的，具体转化关系如下：

```C++
//pageid 页号
//ptr 指针，存放的是地址
const size_t PAGE_SHIFT = 12;//一页的4k
void* ptr = (void*)(pageid << PAGE_SHIFT);
PageID pageid = (PageID)ptr >> PAGE_SHIFT;
```

​		所以哈希表映射关系可变为，**key为：页号，value为：内存大小size**；

​		更近一步，在内存池中我们一般不直接使用size进行内存的管理，而是构造一个结构体Span：Span含有成员变量_objsize，代表所管理的内存大小；

```C++
//Span是一个跨度，既可以分配内存出去，也是负责将内存回收回来到PageCache合并
//是一链式结构，定义为结构体就行，避免需要很多的友元
struct Span
{
	PageID _pageid = 0;//页号
	size_t _npage = 0;//页数

	Span* _prev = nullptr; 
	Span* _next = nullptr;

	void* _list = nullptr;//链接对象的自由链表，后面有对象就不为空，没有对象就是空
	size_t _objsize = 0;//对象的大小----##即上文的size

	size_t _usecount = 0;//对象使用计数,
};
```

​	所以哈希表映射关系可变为，**key为：页号，value为：span指针对象**；

​	**但是**

​	在32位平台下，设一页大小为4K，页的数目就是2^32 / 2^12 = 2^20 ；

​	在64为平台下，设一页大小为4K，页的数目就是2^64/ 2^12 = 2^42；

​	这是非常恐怖的数字，哈希表太大了，会影响整个内存池的性能；这显然是不可行的，因此可使用基数树，基数树实际上就是一个分层的哈希表，根据所分层数不同可分为单层基数树、二层基数树、三层基数树等。

​	当然以上我只是简单说明其中一个原因。

### 2.基数树简介

​	这里以二维基数树简单介绍一下，其实就是简单的两层数组结构，第一层数组大小为2^5,第二层为数组大小2^19；第一层数组存储指向第二层数组的指针，第二层为存储span指针对象；

```C++
//pageid 页号
//ptr 地址
const size_t PAGE_SHIFT = 12;//一页的4k
void* ptr = (void*)(pageid << PAGE_SHIFT);
PageID pageid = (PageID)ptr >> PAGE_SHIFT;


static const int ROOT_BITS = 5;
static const int ROOT_LENGTH = 1 << ROOT_BITS; // 第一层数组大小32

static const int LEAF_BITS = 20 - ROOT_BITS; //15
static const int LEAF_LENGTH = 1 << LEAF_BITS;//第二层为数组大小 32768

 //root_[ROOT_LENGTH]  // 第一层数组
//leaf[ROOT_LENGTH] //第二层为数组
```

​	由上面可知指针ptr和页号pageid的对应关系，那么可根据页号pageid，计算出第一层数组和第二层数组的索引位置;那么就可以利用get函数找到 页号 和 span指针对象的对应关系

```C++
//根据页号pageid --- 这里用k代替，第一层数组和第二层数组的索引位置，
const Number i1 = k >> LEAF_BITS;
const Number i2 = k & (LEAF_LENGTH - 1);

Span* get(Number k) const {
        const Number i1 = k >> LEAF_BITS;
        const Number i2 = k & (LEAF_LENGTH - 1);
        if ((k >> BITS) > 0 || root_[i1] == nullptr) {
            return nullptr;
        }
        return root_[i1]->values[i2];
}
```



![image-20220709155333503](https://gitee.com/caoguangjing/concurrent_memory_pool/raw/master/1657353202521.jpg)



​	当第一层索引位置为null时，建立第二层数组对象；

```C++
void set(Number pageid, Span* v) {
        const Number i1 = pageid >> LEAF_BITS;
        const Number i2 = pageid & (LEAF_LENGTH - 1);
        assert(i1 < ROOT_LENGTH);
        if (Ensure(k) == true) {
            root_[i1]->values[i2] = v;
            ++(root_[i1]->count);
        }
}

bool Ensure(Number pageid) {
        const Number i1 = pageid >> LEAF_BITS;
        // Check for overflow
        if (i1 >= ROOT_LENGTH)
            return false;

        // Make 2nd level node if necessary
        if (root_[i1] == nullptr) { //第一层为null
            Leaf* leaf = new Leaf; // 建立第二层
            if (leaf == nullptr) return false;
            memset(leaf, 0, sizeof(*leaf));
            root_[i1] = leaf;
        }
        return true;
}
```

### 3.快速运行

运行环境：window，32位，

直接使用Visual Studio打开即可