内存池技术畅想-白红宇

内存池技术畅想

阅读量：6092 次

发布时间：2019-06-20

本文共 11272 字，大约阅读时间需要 37 分钟。

内容：

本文将介绍几种常用的内存池技术的实现，这是我最近学习各大开源的内存池技术遗留下来的笔记，其主要内容包括：

- STL内存池以及类STL内存池实现
- Memcached内存池实现
- 固定规格内存池实现
- Nginx内存池实现

一.类STL的内存池实现方式

SGI STL的内存池分为一级配置器和二级配置器，

一级配置器主要处理分配空间大小大于128Byte的需求，其内部实现就是直接使用malloc realloc 和free.

二级配置器则使用使用free_list的数组链表的方式来管理内存，SGI的Allocate最小的分辨单位为8Byte,其free_list数组存着8*n（n=1...16)大小内存的首地址,大小同样的内存块使用链表的形式相连

free_list[0] --------> 8 byte

free_list[1] --------> 16 byte

free_list[2] --------> 24 byte

free_list[3] --------> 32 byte

... ...

free_list[15] -------> 128 byte

因为其对内存的管理的最小分辨度为8Byte,所以当我们申请的内存空间不是8的倍数的时候，内存池会将其调整为8的倍数大小，这叫内存对齐。当然这也免不了带来内存浪费，例如我们只需要一个10Byte的大小，内存池经过内存对齐后，会给我们一个16Byte的大小，而剩余的6Byte，在这次使用中根本没有用到。（对于chunk_allocate的优化请见一文的末尾处）

类STL的内存池一般都有如下API

void* allocate(size_t __n)

//外部API，分配内存

void deallocate(void* __p, size_t __n)

//外部API，回收内存，以供再利用

char* chunk_alloc(size_t __size, int& __nobjs)

//内部函数，用于分配一个大块

void* refill(size_t n) //内部函数，用于allocate从free_list中未找到可使用的块时调用

这种内存池的工作流程大致如下：

外部调用 allocate向内存池申请内存

allocate通过内存对齐的方式在free_list找到合适的内存块链表头

判断链表头是否为NULL,为NULL则表示没有此规格空闲的内存，如果不为NULL，则返那块内存地址，并将此块内存地址移除它对应的链表

如果为NULL，则调用refill在freelist上挂载20个此规格的内存空间（形成链表），也就是保证此规格的内存空间下次请求时够用

refill的内部调用了chunk_alloc函数，chunk_alloc的职责就是负责内存池的所有内存的生产，在生产的时候他为了保证下次能有内存用，所以会将空间*2，所以这个申请流程总的内存消耗为：（对需求规格内存对齐后的大小）*20*2

下面举一个例子来简单得说明一下：

当第一次调用chunk_alloc(32,10)的时候，表示我要申请10块__Obje(free_list)，每块大小32B，此时，内存池大小为0，从堆空间申请32*20的大小的内存，把其中32*10大小的分给free_list[3]。

我再次申请64*5大小的空间，此时free_list[7]为0，它要从内存池提取内存，而此时内存池剩下320B，刚好填充给free_list[7]，内存池此时大小为0。

第三次请求72*10大小的空间，此时free_list[8]为0，它要从内存池提取内存，此时内存池空间不足，再次从堆空间申请72*20大小的空间，分72*10给free_list用。

首次申请20Byte后的状态图：

在未设置预分配的STL内存池中，某个中间状态的整体图

由于STL源码可阅读性不强，各种宏等等满目不堪，所以我这里就不贴SGI 的源码了，我在这里贴一个简单易懂的山寨版本，基本的思路是一模一样的，这个实现没有了一级和二级配置器，而是在需要的时候直接malloc或者从free_list找。

View Code

1 .

2 #ifndef MEMORYPOOL_H

#define MEMORYPOOL_H

5 #include <stdio.h>

6 #include <assert.h>

using

namespace std;

class MemoryPool

11 {

private:

Really we should use static const int x = N

instead of enum { x = N }, but few compilers accept the former.

enum {__ALIGN =

8};

小型区块的上调边界，即小型内存块每次上调8byte

enum {__MAX_BYTES =

128};

小型区块的上界

enum {__NFREELISTS = __MAX_BYTES/__ALIGN};

free-lists的个数，为:16，每个free-list管理不同大小内存块的配置

将请求的内存大小上调整为8byte的倍数，比如8byte, 16byte, 24byte, 32byte

static size_t ROUND_UP(size_t bytes)

22 {

return (((bytes) + __ALIGN-

1) & ~(__ALIGN -

1));

24 }

26 union obj

27 {

28 union obj* free_list_link;

下一个区块的内存地址，如果为NULL，则表示无可用区块

char client_data[

1];

内存区块的起始地址

30 };

private:

static obj *free_list[__NFREELISTS];

__NFREELISTS = 16

free_list[0] --------> 8 byte（free_list[0]管理8bye区块的配置）

free_list[1] --------> 16 byte

free_list[2] --------> 24 byte

free_list[3] --------> 32 byte

... ...

free_list[15] -------> 128 byte

根据区块大小，决定使用第n号的free_list。n = [0, 15]开始

static size_t FREELIST_INDEX(size_t bytes)

45 {

return (((bytes) + __ALIGN-

1)/__ALIGN -

1);

47 }

Returns an object of size n, and optionally adds to size n free list.

static

void *refill(size_t n);

配置一大块空间，可容纳nobjs个大小为size的区块

如果配置nobjs个区块有所不便，nobjs可能会降低

static

char *chunk_alloc(size_t size,

int &nobjs);

Chunk allocation state.

static

char *start_free;

内存池起始位置

static

char *end_free;

内存池结束位置

static size_t heap_size;

内存池的大小

public:

公开接口，内存分配函数

static

void* allocate(size_t n)

65 {

66 obj** my_free_list = NULL;

67 obj* result = NULL;

如果待分配的内存字节数大于128byte,就调用C标准库函数malloc

if (n > (size_t) __MAX_BYTES)

71 {

return malloc(n);

73 }

调整my_free_lisyt，从这里取用户请求的区块

76 my_free_list = free_list + FREELIST_INDEX(n);

79 result = *my_free_list;

欲返回给客户端的区块

if (result ==

没有区块了

82 {

void *r = refill(ROUND_UP(n));

return r;

86 }

88 *my_free_list = result->free_list_link;

调整链表指针，使其指向下一个有效区块

return result;

91 };

归还区块

static

void deallocate(

void *p, size_t n)

96 {

97 assert(p != NULL);

99 obj* q = (obj *)p;

100 obj** my_free_list = NULL;

101

102

大于128byte就调用第一级内存配置器

103

if (n > (size_t) __MAX_BYTES)

104 {

105 free(p) ;

106 }

107

108

寻找对应的free_list

109 my_free_list = free_list + FREELIST_INDEX(n);

110

111

调整free_lis，回收内存

112 q -> free_list_link = *my_free_list;

113 *my_free_list = q;

114 }

115

116

static

void * reallocate(

void *p, size_t old_sz, size_t new_sz);

117

118 } ;

119

120

121

We allocate memory in large chunks in order to avoid fragmenting

122

the malloc heap too much.

123

We assume that size is properly aligned.

124

We hold the allocation lock.

125

126

假设size已经上调至8的倍数

127

注意nobjs是passed by reference,是输入输出参数

128

char* MemoryPool::chunk_alloc(size_t size,

int& nobjs)

129 {

130

char* result = NULL;

131

132 size_t total_bytes = size * nobjs;

请求分配内存块的总大小

133 size_t bytes_left = end_free - start_free;

内存池剩余空间的大小

134

135

if (bytes_left >= total_bytes)

内存池剩余空间满足要求量

136 {

137 result = start_free;

138 start_free += total_bytes;

139

140

return result;

141 }

142

else

if (bytes_left >= size)

内存池剩余空间不能完全满足需求量，但足够供应一个(含)以上的区块

143 {

144 nobjs = bytes_left/size;

计算内存池剩余空间足够配置的区块数目

145 total_bytes = size * nobjs;

146

147 result = start_free;

148 start_free += total_bytes;

149

150

return result;

151 }

152

else

内存池剩余空间连一个区块都无法提供

153 {

154

bytes_to_get为内存池向malloc请求的内存总量

155 size_t bytes_to_get =

2 * total_bytes + ROUND_UP(heap_size >>

4);

156

157

Try to make use of the left-over piece.

158

if (bytes_left >

159 {

160 obj** my_free_list = free_list + FREELIST_INDEX(bytes_left);

161

162 ((obj *)start_free) -> free_list_link = *my_free_list;

163 *my_free_list = (obj *)start_free;

164 }

165

166

调用malloc分配堆空间，用于补充内存池

167 start_free = (

char *)malloc(bytes_to_get);

168

if (

0 == start_free)

heap空间已满，malloc分配失败

169 {

170

int i;

171 obj ** my_free_list, *p;

172

173

遍历free_list数组，试图通过释放区块达到内存配置需求

174

for (i = size; i <= __MAX_BYTES; i += __ALIGN)

175 {

176 my_free_list = free_list + FREELIST_INDEX(i);

177 p = *my_free_list;

178

179

if (

0 != p)

180 {

181 *my_free_list = p -> free_list_link;

182 start_free = (

char *)p;

183 end_free = start_free + i;

184

185

return chunk_alloc(size, nobjs);

186

Any leftover piece will eventually make it to the

187

right free list.

188 }

189 }

190

191 end_free =

In case of exception.

192

193

调用第一级内存配置器，看看out-of-memory机制能否尽点力

194

195

This should either throw an

196

exception or remedy the situation. Thus we assume it

197

succeeded.

198 }

199

200 heap_size += bytes_to_get;

201 end_free = start_free + bytes_to_get;

202

203

return chunk_alloc(size, nobjs);

204 }

205

206 }

207

208

209

Returns an object of size n, and optionally adds to size n free list.

210

We assume that n is properly aligned.

211

We hold the allocation lock.

212

void* MemoryPool::refill(size_t n)

213 {

214

int nobjs =

20;

215

216

注意nobjs是输入输出参数，passed by reference。

217

char* chunk = chunk_alloc(n, nobjs);

218

219 obj* * my_free_list = NULL;

220 obj* result = NULL;

221 obj* current_obj = NULL;

222 obj* next_obj = NULL;

223

int i;

224

225

如果chunk_alloc只获得了一个区块，这个区块就直接返回给调用者，free_list无新结点

226

if (

1 == nobjs)

227 {

228

return chunk;

229 }

230

231

调整free_list，纳入新结点

232 my_free_list = free_list + FREELIST_INDEX(n);

233

234 result = (obj*)chunk;

这一块返回给调用者(客户端)

235

236

237

用chunk_alloc分配而来的大量区块配置对应大小之free_list

238 *my_free_list = next_obj = (obj *)(chunk + n);

239

240

for (i =

1; ; i++)

241 {

242 current_obj = next_obj;

243 next_obj = (obj *)((

char *)next_obj + n);

244

245

if (nobjs -

1 == i)

246 {

247 current_obj -> free_list_link = NULL;

248

break;

249 }

250

else

251 {

252 current_obj -> free_list_link = next_obj;

253 }

254 }

255

256

return result;

257 }

258

259

重新配置内存，p指向原有的区块，old_sz为原有区块的大小，new_sz为新区块的大小

260

void* MemoryPool::reallocate(

void *p, size_t old_sz, size_t new_sz)

261 {

262

void* result = NULL;

263 size_t copy_sz =

264

265

if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES)

266 {

267

return realloc(p, new_sz);

268 }

269

270

if (ROUND_UP(old_sz) == ROUND_UP(new_sz))

271 {

272

return p;

273 }

274

275 result = allocate(new_sz);

276 copy_sz = new_sz > old_sz? old_sz : new_sz;

277

278 memcpy(result, p, copy_sz);

279

280 deallocate(p, old_sz);

281

282

return result;

283 }

284

285

静态成员变量初始化

286

char* MemoryPool::start_free =

287

288

char* MemoryPool::end_free =

289

290 size_t MemoryPool::heap_size =

291

292 MemoryPool::obj* MemoryPool::free_list[MemoryPool::__NFREELISTS]

293 = {

0, };

294

295

#endif

296

二.MemCached内存池实现

与类STL内存池不同的是，用于缓存的内存池不是解决小对象的内存分配可能导致堆内存碎片多的问题，缓存内存池要为缓存系统的所有存储对象分配空间，无论大小。因为缓存系统通常对其占用的最大内存有限制，所以也就不能在没有空间用的时候随便malloc来实现了。 MemCached的内存池的基本想法是避免重复大量的初始化和清理操作。

Memcached 中内存分配机制主要理念

1. 先为分配相应的大块内存，再在上面进行无缝小对象填充

2. 懒惰检测机制，Memcached 不花过多的时间在检测各个item对象是否超时，当 get获取数据时，才检查item对象是否应该删除，你不访问，我就不处理。

3. 懒惰删除机制，在 memecached 中删除一个 item对象的时候，并不是从内存中释放，而是单单的进行标记处理，再将其指针放入 slot回收插糟，下次分配的时候直接使用。

MemCached内存池Slab Allocation的主要术语

Page

分配给Slab的内存空间，默认是1MB。分配给Slab之后根据slab的大小切分成chunk。

Chunk

用于缓存记录的内存空间。

Slab Class

特定大小的chunk的组。

Memcached的内存分配以page为单位，默认情况下一个page是1M ，可以通过-I参数在启动时指定。如果需要申请内存时，memcached会划分出一个新的page并分配给需要的slab区域。Memcached并不是将所有大小的数据都放在一起的，而是预先将数据空间划分为一系列slabs，每个slab只负责一定范围内的数据存储，其大小可以通过启动参数设置增长因子，默认为1.25，即下一个slab的大小是上一个的1.25倍。如下图，每个slab只存储大于其上一个slab的size并小于或者等于自己最大size的数据。如下图所示，需要存储一个100Bytes的对象时，会选用112Bytes的Slab Classes

基于这种实现的内存池也会遇到STL内存池一样的问题，那就是资源的浪费，我只需要100Byte的空间，你却给了我128Bytes,剩余的28Bytes就浪费了

其主要API：

slabs_init()

slab初始化，如果配置时采用预分配机制(prealloc)则在先在这使用malloc分配所有内存。

再根据增长因子factor 给每个 slabclass 分配容量。

slabs_clsid()

计算出哪个 slabclass 适合用来储存大小给定为 size的item，如果返回值为 0则存储的物件过大，无法进行存储。

do_slabs_alloc()

在这个函数里面，由宏定义来决定采用系统自带的 malloc 机制还是 memcached的slab机制对内存进行分配，理所当然，在大多数情况下，系统的malloc会比slab慢上一个

数量级。分配时首先考虑slot 内的空间(被回收的空间),再检查 end_page_ptr 指针指向的的空闲空间，还是没有的空间的话，再试试分配新的内存。如果所有空间都用尽的

时候，

则返回NULL表示目前资源已经枯竭了。

do_slabs_free()

首先检查当目前的插糟是否已经达到可用总插糟的总容量，如果达到就为其重新分配空间，再将该回收的 item的指针插入对应当前 id的 slabclass 的插糟（slots）之中。

关于MemCached还有个问题需要解释下，在预分配的场景下，有的同事认为MemCached不适合大量存储某个特定大小范围内的对象，他们认为预分配的条件下，每个SlabClasses的总大小是固定的（为一个Page),其实不是，MemCached预分配并不会消耗掉所有的内存，在请求空间的时候，如果发现这个型号的Chunks都被用完了，就会新增一个分页到这个Slab Classes，所以是不会出现那位同事说的那个问题的...（可见代码slabs.c中do_slabs_alloc函数中do_slabs_newslab的调用）

三.固定大小内存池

上面两种内存池的实现，都会造成一定程度的内存浪费，如果我存的对象大小基本是固定的，尽管有很多不同的对象，有没有不会浪费内存的的简单方式呢？

既然需要存的对象大小是固定的，那么我们的内存池对于内存的管理可以这样实现：

class IovecContainer

{

public:

list<char*> m_objList;

};

class MemoryPool

{

public:

void* allocate(size_t __n)

//外部API，分配内存

void deallocate(void* __p, size_t __n)

//外部API，回收内存，以供再利用

private:

map<int, IovecContainer* > m_mapPool;

char* chunk_alloc(size_t __size, int& __nobjs)//内部函数，用于分配一个大块

void* refill(size_t n) //内部函数，用于allocate从free_list中未找到可使用的块时调用

};

这样的实现对于这个特定的需求非常好用,不回浪费掉剩余空间，但是这样的实现局限性就高了，我们不能用这个内存池来存储大小不定的对象（如string)，如果用了，此内存池形同虚设，并且还浪费内存，所以具体怎么选择还是要看需求来定...

四.Nginx内存池实现

关于Nginx内存池实现网上有比较多的分析文章，这里我就不重复造轮子了，直接贴链接，有兴趣的可以关注下：

http://blog.csdn.net/v_july_v/article/details/7040425

http://bbs.chinaunix.net/thread-3626006-1-1.html；

http://blog.csdn.net/livelylittlefish/article/details/6586946；

http://blog.chinaunix.net/space.php?uid=7201775；

淘宝数据共享平台博客：http://www.tbdata.org/archives/1390