Study Note

Haproxy实现了自己的内存管理，为经常使用的数据结构维护一个内存池，把所有的内存池再串起来，申请和释放内存时，首先到该内存池链表中查找该类型的内存池是否有空闲内存，有的话直接使用，没有的话再重新分配,代码主要在src/Memory.c中
Haproxy中的内存池结构是：

struct pool_head {
void **free_list;
struct list list; /* list of all known pools */
unsigned int used; /* how many chunks are currently in use */
unsigned int allocated; /* how many chunks have been allocated */
unsigned int limit; /* hard limit on the number of chunks */
unsigned int minavail; /* how many chunks are expected to be used */
unsigned int size; /* chunk size */
unsigned int flags; /* MEM_F_* */
unsigned int users; /* number of pools sharing this zone */
char name[12]; /* name of the pool */
};

used，allocated，limit，minavail，size，users，是某个具体内存池使用情况的计数器，flags可以设置该内存池是否可以共享使用（MEM_F_SHARED）。
haproxy的list结构比较简单，是一个双向链表，通过list数据结构达到串起来的目的。

struct list {
struct list *n; /* next */
struct list *p; /* prev */
};

因此haproxy的内存池数据结构如下：

• pool创建

struct pool_head *create_pool(char *name, unsigned int size, unsigned int flags)
{
	struct pool_head *pool;
	struct pool_head *entry;
	struct list *start;
	unsigned int align;

	/* We need to store at least a (void *) in the chunks. Since we know
	 * that the malloc() function will never return such a small size,
	 * let's round the size up to something slightly bigger, in order to
	 * ease merging of entries. Note that the rounding is a power of two.
	 */

	align = 16;
	size  = (size + align - 1) & -align;

	start = &pools;
	pool = NULL;

	list_for_each_entry(entry, &pools, list) {
		if (entry->size == size) {
			/* either we can share this place and we take it, or
			 * we look for a sharable one or for the next position
			 * before which we will insert a new one.
			 */
			if (flags & entry->flags & MEM_F_SHARED) {
				/* we can share this one */
				pool = entry;
				DPRINTF(stderr, "Sharing %s with %s\n", name, pool->name);
				break;
			}
		}
		else if (entry->size > size) {
			/* insert before this one */
			start = &entry->list;
			break;
		}
	}

	if (!pool) {
		pool = CALLOC(1, sizeof(*pool));
		if (!pool)
			return NULL;
		if (name)
			strlcpy2(pool->name, name, sizeof(pool->name));
		pool->size = size;
		pool->flags = flags;
		#ifdef USE_MEM_POOL3
		LIST_INIT(&pool->free_block_list);
		#endif
		LIST_ADDQ(start, &pool->list);
	}
	pool->users++;
	return pool;
}

分配一个内存池时，需要指定名称name，大小size和标记flag。
pools是一个全局变量，指向内存池链表的头，遍历内存池链表，如果有块大小相同的并且可以共用的内存池，更新users数目，如果没有可共用的内存池，则新建一个名为name的内存池，设置size，name和users=1。
注意，内存池链表按照size从小到大排列，每次会调整头pools的位置，在适合的位置插入新的pool。

• pool销毁

void *pool_destroy2(struct pool_head *pool)
{
	if (pool) {
		pool_flush2(pool);
		if (pool->used)
			return pool;
		pool->users--;
		if (!pool->users) {
			LIST_DEL(&pool->list);
			FREE(pool);
		}
	}
	return NULL;
}

内存池销毁时，指定一个pool，首先free该pool的freelist，通过pool_flush2实现：

void pool_flush2(struct pool_head *pool)
{
	void *temp, *next;
	if (!pool)
		return;

	next = pool->free_list;
	while (next) {
		temp = next;
		next = *(void **)temp;
		pool->allocated--;
		FREE(temp);
	}
	pool->free_list = next;

	/* here, we should have pool->allocate == pool->used */
}

free_list中释放后，如果该pool还有内存在被使用（used != 0），则返回，否则判断该pool是否有其它数据结构共享，如果users为0，则彻底删除该pool

• 内存申请

#define pool_alloc2(pool)                                       \
({                                                              \
        void *__p;                                              \
        if ((__p = pool->free_list) == NULL)                    \
                __p = pool_refill_alloc(pool);                  \
        else {                                                  \
                pool->free_list = *(void **)pool->free_list;    \
                pool->used++;                                   \
        }                                                       \
        __p;                                                    \
})

首先从pool的free_list中取得第一个空闲内存块，分配之，注意此处直接把free_list的下一个空闲块的地址写在的上一个空间开头处，相当于实现了next的机制；如果为空，则调用pool_refill_alloc进行释放和重新分配：

void *pool_refill_alloc(struct pool_head *pool)
{
	void *ret;

	if (pool->limit && (pool->allocated >= pool->limit))
		return NULL;
	ret = MALLOC(pool->size);
	if (!ret) {
		pool_gc2();
		ret = MALLOC(pool->size);
		if (!ret)
			return NULL;
	}
	pool->allocated++;
	pool->used++;
	return ret;
}

其中pool_gc2是对pools所有的内存池的free_list进行相应的free，以空出新的内存供MALLOC。

• 内存释放

#define pool_free2(pool, ptr)                           \
({                                                      \
        if (likely((ptr) != NULL)) {                    \
                *(void **)ptr = (void *)pool->free_list;\
                pool->free_list = (void *)ptr;          \
                pool->used--;                           \
        }                                               \
})

释放时，将该内存放到该pool的空闲列表，注意此处把free_list的地址写到的要free的空间的头部，然后把free_list指向了该内存地址ptr，，并不真正的free，而是把空间保留下来已被后用，这也是haproxy的一个策略。