内存池介绍

发表于 2017-11-06 更新于 2022-10-09 分类于设计

内存池

buffer/cache/pool

cache（高速缓存）是一种介于寄存器和内存之间的存储器，访问速度也在他们二者之间，当用户程序请求存储空间时，会先尝试从 cache 获取，当找不到时再到内存中找，并且找到的页及其临近的几页都会被拿到 cache 中去以备下次访问。
而 buffer 出现的地方比较多，比如 java4 引入的 NIO 中就有一个 Buffer，它的主要作用是缓冲从 Channel 中取到的数据，服务器接收到网络请求时从准备到开始接收数据是有一定的时延的，当出现大量的小请求时，很容易造成资源的浪费，所以引入了缓冲区。
pool 常出现在一些框架中，常见的有数据库连接池、内存池，它和 buffer 有些区别，pool 中的对象往往可以重复利用。

malloc/free

通过调用 malloc 和 free 函数可以实现在堆上的对象分配，这是 C 语言标准库提供的最基本的手动管理内存分配的方法，但是 malloc/free 实现的其实是最基本的 指针碰撞（Bump the Pointer） 内存分配方式，每次分配时都会从空闲块链表表头开始搜索，找到足够大的一块就返回，释放时同样是在空闲块链表中遍历，找到它的分配位置，再和前后两块合并。

显然，这种方式存在一些缺陷：

大量分配后空闲块链表变得很长（时间开销）
产生大量内存碎片（空间开销）
使用麻烦，容易造成内存泄露（申请后忘了释放）

下面是一种 malloc/free 的实现：

折叠/展开代码

typedef long Align; //最受限类型

union header{ //块头部
    struct{
        union header *ptr; //空闲块链表的下一块
        unsigned size; //本块的大小
    }s;
    Align x; //强制块对齐，即强制header最小不小于Align
};
typedef union header Header;
/******************************************/
#define MAXBYTES (unsigned)10240

static Header base;//链表
static Header *freep = NULL;//空闲链表的初始指针

/* malloc函数：存储分配 */
void *malloc(unsigned nbytes){
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;
    
    //超出可分配字节数上限
    if(nbytes > MAXBYTES){
        fprintf(stderr, "alloc: can't allocate more than %u bytes\n", MAXBYTES);
        return NULL;
    }

    //需要分配的块数
    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    //空闲链表不存在
    if((prevp = freep) == NULL){
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        //足够分配
        if(p->s.size >= nunits){
            if(p->s.size == nunits){
                prevp->s.ptr = p->s.ptr;
            }
            else{
                //如果找到的块太大，则分配其末尾部分
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void*)(p + 1);
        }
        //闭环的空闲链表
        if(p == freep){
            if((p = morecore(nunits)) == NULL){
                return NULL;//系统无剩余存储空间
            }
        }
    }
}

#define NALLOC 1024 //最小申请单元数
static unsigned maxalloc; //当前已分配的最大内存块的长度
/* morecore函数：向系统申请更多的存储空间 */
Header *morecore(unsigned nu){
    char *cp, *sbrk(int);
    Header *up;
    
    if(nu < NALLOC){
        nu = NALLOC;
    }
    cp = sbrk(nu * sizeof(Header));
    if(cp == (char*) - 1){ //没有空间
        return NULL;
    }
    up = (Header*)cp;
    up->s.size = nu;
    maxalloc = (up->s.size > maxalloc) ? up->s.size : maxalloc;
    //把多余的存储空间插入到空闲区域
    free((void*)(up + 1));
    return freep;
}

/* free函数：将块ap放入空闲块链表中 */
void free(void *ap){
    Header *bp, *p;
    
    bp = (Header*)ap - 1; //块头
    //欲free的内存块长度不能等于0或者大于当前已分配的最大内存块长度
    if(bp->s.size == 0 || bp->s.size > maxalloc){
        fprintf(stderr, "free: can't free %u units\n", bp->s.size);
        return ;
    }
    //扫描空闲块链表，找到bp所处位置，它可能在两个空闲块之间，也可能在链表末尾
    for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr){
        //被释放的块在链表的开头或末尾
        if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)){
            break;
        }
    }
    //与上一相邻（空闲）块合并
    if(bp + bp->s.size == p->s.ptr){
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    }
    else{//说明中间有已经分配的块
        bp->s.ptr = p->s.ptr;
    }
    //与下一相邻（空闲）块合并
    if(p + p->s.size == bp){
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    }
    else{//说明中间有已经分配的块
        p->s.ptr = bp;
    }
}

简单的测试：

折叠/展开代码

typedef struct MyList {
    int val;
    struct MyList *next;
} MyList;

int main(int argc, char *argv[]) {
    int n = 1000000;
    while(n--) {
        MyList *list = malloc(sizeof(MyList));
        free(list);
    }
    return 0;
}

设计简单内存池

内存池和线程池或数据库连接池（各种池）的实现机制类似，都是事先申请一大块资源，当实际使用时，不必再去申请内存，而是直接从内存池中“拿”，如果内存池设计得好，完全可以避免直接使用 malloc/free 进行内存管理的问题。

下面的代码很大程度上参考了这里的实现

折叠/展开代码

mem_pool.h
#ifndef _MEM_POOL_H
#define _MEM_POOL_H

#define BLOCKHEAD_SIZE 24 // 两个地址值合为16位，再加上8位验证码
#define MAGIC_CODE 0x123456 // 验证码（用于free内存块的时候判断是否是合法的内存块）

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

/**
 * 内存块
 * 1.data包含head和body两部分
 * head包括指向对应block的指针、对应list的指针及验证码（MAGIC_CODE）
 * 2.双向链表
 * 为了free时方便从used中拿出插入到free中
 */
typedef struct MemBlock {
    void *data;
    struct MemBlock *prev, *next;
} MemBlock;
static MemBlock *newMemBlock(int size) {
    MemBlock *block = malloc(sizeof(MemBlock));
    if(! block) {
        perror("malloc MemBlock failed");
        return NULL;
    }
    block->data = malloc(BLOCKHEAD_SIZE + size);
    return block;
}
/**
 * 内存表
 * 1.每个list保存一种size的内存块
 */
typedef struct MemList {
    MemBlock *free, *used;
    int size;
    struct MemList *next;
} MemList;
static MemList *newMemList(int size) {
    MemList *list = malloc(sizeof(MemList));
    if(! list) {
        perror("malloc MemList failed");
        return NULL;
    }
    list->size = size;
    return list;
}
/**
 * 内存池
 * 1.单例（因为是C语言，所以还未实现）
 * 1.蝇量
 */
typedef struct MemPool {
    MemList *head;
    MemList *last;
} MemPool;
static MemPool *newMemPool() {
    MemPool *pool = malloc(sizeof(MemPool));
    if(! pool) {
        perror("malloc MemPool failed");
        return NULL;
    }
    return pool;
}

void* getBuf(MemPool *pool, size_t bufSize);
int freeBuf(void *buf);

#endif // _MEM_POOL_H

#include "mem_pool.h"

/**
 * 把内存块想象成一个int64的数组，头三个元素（head）为元数据，
 * 之后的部分为分配给用户实际可用的内存
 */
void setMemoryHead(void *buf, MemList *list, MemBlock *block) {
    if(buf == NULL) {return ;}
    int64_t *data = (int64_t *)buf;
    // 设置头部，注意指针有64位
    data[0] = (int64_t)list;
    data[1] = (int64_t)block;
    data[2] = (int64_t)MAGIC_CODE;
}
void* getMemoryBody(void *buf) {
    if(buf == NULL) {return NULL;}
    int64_t *data = (int64_t *)buf;
    return &data[3];
}
/**
 * 从释放的内存块中可以找到它所属的list和block节点位置
 * @return 0表示失败，其他表示成功
 */
int getFromBuf(void *buf, MemList** list, MemBlock** block) {
    // 先转换为字节数组再计算到头部的偏移量，因为
    char* cbuf = buf;
    int64_t *data = (int64_t *)(buf - BLOCKHEAD_SIZE);
    if(data[2] != MAGIC_CODE) {
        perror("error: not a valid block");
        return 0;
    }
    // 还原
    *list = data[0];
    *block = data[1];
    return 1;
}

/**
 * 从内存池中获取一块内存
 * 内存块的大小是固定的，链表的每个节点代表一种大小的内存块
 */
void* getBuf(MemPool *pool, size_t bufSize) {
    if(! pool) {return NULL;}
    // list为空，表示还未分配过，尝试分配并初始化
    if(! pool->head) {
        pool->head = newMemList(bufSize);
    }
    MemList *list = pool->head;

    // 查找匹配大小的list
    while(list && list->size != bufSize) {
        list = list->next;
    }

    // 没有匹配的list，分配一个，插入到表头处
    if(! list) {
        MemList *tmp = newMemList(bufSize);
        tmp->next = pool->head;
        pool->head = tmp;
        list = tmp;
    }

    // 查找已有list中是否存在空余内存块，若没有则新建
    if(! list->free) {
        list->free = newMemBlock(list->size);
    }

    // 取一块
    MemBlock *block = list->free;
    list->free = block->next;
    if(list->free) {
        list->free->prev = NULL;
    }
    // 压回已使用块表
    if(list->used) {
        list->used->prev = block;
    }
    block->next = list->used;
    list->used = block;

    // 设置块头部
    setMemoryHead(block->data, list, block);
    return getMemoryBody(block->data);
}

/**
 * 释放一块内存
 * @return 0表示释放失败，其他数字表示成功
 */
int freeBuf(void *buf) {
    MemList *list = NULL;
    MemBlock *block = NULL;
    if(! getFromBuf(buf, &list, &block)) {
        return 0;
    }

    // 从used块中取出
    if(block->prev) {
        block->prev->next = block->next;
    }
    if(block->next) {
        block->next->prev = block->prev;
    }
    // 放到free块中
    if(list->free) {
        list->free->prev = block;
    }
    block->next = list->free;
    block->prev = NULL;
    list->free = block;

    // 操作成功
    return 1;
}

简单的测试：

折叠/展开代码

typedef struct List {
    int val;
    struct List *next;
} List;

int main() {
    MemPool *pool = newMemPool();
    time_t begin, end;
    time(&begin);
    srand(time(0));
    List *list = NULL;
    int n = 100000000;
    while(n--) {
        if(random() % 10 < 7) {
            List *node = getBuf(pool, sizeof(List));
            node->next = list;
            list = node;
        } else if(list) {
            List *node = list;
            list = list->next;
            freeBuf(node);
        }
    }
    time(&end);
    printf("OK\n");
    printf("costs %lf\n", difftime(end, begin));
    return 0;
}

可改进的地方：

线程安全，这里有个问题，是把整个池锁住还是把其中的某个表锁住？因为内存池是使用很频繁的，我更倾向于后者（锁住某个表的实现可以参考 Java 的分段锁机制）
一种 size 一个 list，各 list 之间用链表串联起来，如果申请的内存块大小不固定也可能出现这个链表特别长的情况，那样就退化成了 malloc/free，我觉得解决办法是将分配的内存块大小固定成 1024B、2048B 这些量级，但这样又会多出很多内存碎片，又退化成了 malloc/free
引入引用计数或可达性分析算法来管理内存，但是那样的话需要给所有类做一个公共基类，然后重载基类的’=’操作符用于修改引用数，非常麻烦，但是不这么做就退化成了 malloc/free
老实说这个内存池并没有实用价值

一些框架中的内存管理

Doug Lee 的 malloc/free
？？？
Apache 内存池
Apache 内存池的实现相对上面的来说有很多改进

使用一个free数组来表示上面的MemList，下标每增加 1，内存节点大小增加 4K，这样可以很快定位到要分配的那个内存块链表，如果要分配的内存大小超出数组范围就直接分配到下标 0 处，所以不会有溢出的问题
节点大小和下标间的转换用到了一个宏APR_ALIGN，使用该宏要求size为整数，boundary为 2 的幂，具体执行过程还是自己代入一组值算一算
1
2
#define APR_ALIGN(size, boundary) \
(((size)+ ((boundary) - 1)) &~((boundary) - 1))
没有 used 表，分配时就从 free 中取出来返回给用户，找不到就 malloc 一个，释放时插回到 free 表中
用 current_free_index 和 max_free_index 配合限制内存分配器总共能够分配的内存大小

cocos2d-x 内存管理
对 cocos2d-x 的使用经历比较短，不能很好体会它的设计理念，只列出我记得的一些点：

C++11 下本地存储（栈）比堆存储好，最好不要 new 对象
cocos2d-x 使用引用计数算法管理内存，大部分内置对象都继承自 cocos2d::Object 类

MySQL 内存池
MySQL 使用二级缓存机制管理分配的对象，第一级为缓冲池和通用内存池，他们都通过调用 malloc/free 来从操作系统分配/释放内存块，他们的区别下面再讲；第二级为内存堆，它为其他模块提供内存块分配功能

缓冲池（innobase/buf/buf0buf.c、innobase/include/buf0buf.h）
缓冲池的定义如下

通用内存池（innobase/mem/mem0pool.c、innobase/include/mem0pool.h）
内存池的定义如下

折叠/展开代码

struct mem_pool_struct{
	byte*		buf;		/* memory pool */
	ulint		size;		/* memory common pool size */
	ulint		reserved;	/* amount of currently allocated
					memory */
	mutex_t		mutex;		/* mutex protecting this struct */
	UT_LIST_BASE_NODE_T(mem_area_t)
			free_list[64];	/* lists of free memory areas: an
					area is put to the list whose number
					is the 2-logarithm of the area size */
};

内存池的创建函数如下所示

折叠/展开代码

mem_pool_t*
mem_pool_create(
/*============*/
			/* out: memory pool */
	ulint	size)	/* in: pool size in bytes */
{
	mem_pool_t*	pool;
	mem_area_t*	area;
	ulint		i;
	ulint		used;

	ut_a(size > 10000);
	
	pool = ut_malloc(sizeof(mem_pool_t));

	/* We do not set the memory to zero (FALSE) in the pool,
	but only when allocated at a higher level in mem0mem.c.
	This is to avoid masking useful Purify warnings. */

	pool->buf = ut_malloc_low(size, FALSE);
	pool->size = size;

	mutex_create(&(pool->mutex));
	mutex_set_level(&(pool->mutex), SYNC_MEM_POOL);

	/* Initialize the free lists */

	for (i = 0; i < 64; i++) {

		UT_LIST_INIT(pool->free_list[i]);
	}

	used = 0;

	while (size - used >= MEM_AREA_MIN_SIZE) {

		i = ut_2_log(size - used);

		if (ut_2_exp(i) > size - used) {

			/* ut_2_log rounds upward */
		
			i--;
		}

		area = (mem_area_t*)(pool->buf + used);

		mem_area_set_size(area, ut_2_exp(i));
		mem_area_set_free(area, TRUE);

		UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area);

		used = used + ut_2_exp(i);
	}

	ut_ad(size >= used);

	pool->reserved = 0;
	
	return(pool);
}

由此可以得出通用内存池和缓冲池之间的差别

内存堆（innobase/mem/mem0mem.c、innobase/include/mem0mem.h、innobase/include/mem0mem.ic）
内存堆的定义如下
折叠/展开代码
1
2
/* A memory heap is a nonempty linear list of memory blocks */
typedef mem_block_t mem_heap_t;
可见内存堆就是内存块的链表。

内存块（memory block）的定义如下

折叠/展开代码

struct mem_block_info_struct {
	ulint   magic_n;/* 魔数用于debug（标志该块内存是从我这分出去的） *//* magic number for debugging */
	char	file_name[8];/* 创建内存堆的代码文件名 *//* file name where the mem heap was created */
	ulint	line;	/* 创建内存堆的代码行 *//* line number where the mem heap was created */
	UT_LIST_BASE_NODE_T(mem_block_t) base; /* 在第一块（表头）中定义，保存内存块链表的一些元信息，
                        包括长度、表头指针、表尾指针 */
                        /* In the first block in the
			the list this is the base node of the list of blocks;
			in subsequent blocks this is undefined */
	UT_LIST_NODE_T(mem_block_t) list; /* 内存块的链表（双向链表） *//* This contains pointers to next
			and prev in the list. The first block allocated
			to the heap is also the first block in this list,
			though it also contains the base node of the list. */
	ulint   len;    /* 当前内存块大小，以字节为单位 *//* physical length of this block in bytes */
	ulint 	type; 	/* 该内存堆的类型，内存堆的主要分类依据是：从通用内存池还是缓冲池分配 */
                        /* type of heap: MEM_HEAP_DYNAMIC, or
			MEM_HEAP_BUF possibly ORed to MEM_HEAP_BTR_SEARCH */
	ibool	init_block; /* TRUE if this is the first block used in fast
			creation of a heap: the memory will be freed
			by the creator, not by mem_heap_free */
	ulint   free;   /* 当前空闲空间位置 */
                        /* offset in bytes of the first free position for
			user data in the block */
	ulint   start;  /* the value of the struct field 'free' at the 
			creation of the block */
	byte* 	free_block;
			/* if the MEM_HEAP_BTR_SEARCH bit is set in type,
			and this is the heap root, this can contain an
			allocated buffer frame, which can be appended as a
			free block to the heap, if we need more space;
			otherwise, this is NULL */
#ifdef MEM_PERIODIC_CHECK	
	UT_LIST_NODE_T(mem_block_t) mem_block_list;
			/* List of all mem blocks allocated; protected
			by the mem_comm_pool mutex */
#endif
};

内存块的创建函数如下所示

折叠/展开代码

UNIV_INLINE
mem_heap_t*
mem_heap_create_func(
/*=================*/
				/* out, own: memory heap */
	ulint	n,		/* in: desired start block size,
				this means that a single user buffer
				of size n will fit in the block, 
				0 creates a default size block;
				if init_block is not NULL, n tells
				its size in bytes */
	void*	init_block,	/* in: if very fast creation is
				wanted, the caller can reserve some
				memory from its stack, for example,
				and pass it as the the initial block
				to the heap: then no OS call of malloc
				is needed at the creation. CAUTION:
				the caller must make sure the initial
				block is not unintentionally erased
				(if allocated in the stack), before
				the memory heap is explicitly freed. */
	ulint	type,		/* in: MEM_HEAP_DYNAMIC, or MEM_HEAP_BUFFER
				possibly ORed to MEM_HEAP_BTR_SEARCH */
	char*  	file_name,	/* in: file name where created */
	ulint	line		/* in: line where created */
	)
{
	mem_block_t*   block; 

	if (n > 0) {
                // 创建指定大小的内存块
		block = mem_heap_create_block(NULL, n, init_block, type,
							file_name, line);
	} else {
		// 以默认的大小创建，MEM_BLOCK_START_SIZE的值为64B
		block = mem_heap_create_block(NULL, MEM_BLOCK_START_SIZE, 
					init_block, type, file_name, line);
	}

	ut_ad(block);

	UT_LIST_INIT(block->base);

	/* Add the created block itself as the first block in the list */
	UT_LIST_ADD_FIRST(list, block->base, block);

	#ifdef UNIV_MEM_DEBUG

	if (block == NULL) {

		return(block);
	}

	mem_hash_insert(block, file_name, line);

	#endif
	
	return(block);
}

当想要扩增内存堆时调用，它会将扩增的内存块插入内存堆的末尾（mem_block_info_struct 结构中的 base 成员变量包含了表尾指针），而且每次扩增的内存块大小为前一次的两倍大

内存池和 GC 的关系
在阅读《垃圾回收的算法与实现》时，除了某人用 GC 交到了女朋友外，使我最印象深刻的应该是前言中一位教授对 GC 和虚拟内存关系的看法：

既然话说到这里了,我就再介绍一下我的个人看法吧。实际上,GC 相当于虚拟内存。一般的虚拟内存技术是在较小的物理内存的基础上,利用辅助存储创造一片看上去很大的“虚拟”地址空间。也就是说,GC 是扩大内存空间的技术,因此我称其为空间性虚拟存储。这样一来,GC 就成了永久提供一次性存储空间的时间轴方向的时间性虚拟存储。神奇的是,比起称为“垃圾回收”,把 GC 称为“虚拟内存”令人感觉其重要了许多。当初人们根据计算机体系结构开发了许多关于空间性虚拟存储的支持,所以大部分的计算机都标配了空间性虚拟存储。只要硬件支持,GC 性能就能稳步提升,然而现实情况是几乎没有支持 GC 的硬件,这不能不令人感到遗憾。

什么时候使用内存池及一些要点

小心内存泄露
如果应用从内存池中获取对象后没有释放回去就很有可能会发生内存泄露的情况，和 C 语言中 malloc 后忘了 free 的情况类似。一般内存池都是单例的，这意味着内存池和整个应用的生命周期是相同的，这块没被释放的内存将一直占用内存空间，而且因为内存池中总是有对这个对象的引用，所以就算有 GC 也没有办法进行回收。
水平有限我仅谈谈在 Web 应用中的几个解决办法：
- 缩短内存池的生命周期，比如在一次会话期间占用一个内存池，这个内存池将会被保存在一个 SessionContext 对象中，当会话结束时就释放它
- 在一些对象价值不是特别高的情形下（比如），可以使用 弱引用对象池 来管理对象？？？

参考

《C 程序设计语言》
内存池的实现 http://www.cnblogs.com/bangerlee/archive/2011/08/31/2161421.html
A memory pool written with C++ https://github.com/bangerlee/mempool
MySQL 内核 InnoDB 存储引擎
https://www.zhihu.com/question/26190832/answer/32387918
《垃圾回收的算法与实现》