纯C实现内存池

1.介绍

        内存池，池式结构三幻神之一，它拥有池式结构的设计初衷，为了管理和重用一组初始化的对象或资源，但作者认为，它更重要的初衷应该是一种虚拟内存的管理组件，对于需要长时间运行的程序尽可能的避免出现内存碎片。

2.设计思路

        内存池可以分为两种，定长和不定长，定长的实现非常简单，今天的挑战的是不定长的内存池，为了管理不定长的内存块，我们设定一个界限，来把分配的内存块划定为大块和小块，对于大块我们直接分配和释放，对于小块我们分配一个大块用来管理，当小块全部释放回收时，我们再重置指针，以此来做到内存复用，max的值我们取2的次幂，具体架构如下图：

3.代码实现  

        根据上图我们先来定义出对应的结构体：

#include <stddef.h>

typedef struct mp_large_s {
	mp_large *next;
	void *alloc;
} mp_large;

typedef struct mp_node_s {
    mp_node *next;
	unsigned char *last;
	unsigned char *end;
	
	size_t failed;
} mp_node;

typedef struct mp_pool_s {
	size_t max;
	
	mp_large *large;
    mp_node *current;

	mp_node head[0];
} mp_pool;

        再来实现对外接口：

#include <string.h>
#include <stdlib.h>

void *mp_alloc(mp_pool *pool, size_t size);

static size_t next_power_of_two(size_t n) {
    if (n == 0) {
        return 1; // 特殊情况处理
    }
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n |= n >> 32; // 对于64位系统

    n++;
    return n;
}

static void *mp_alloc_block(mp_pool *pool, size_t size) {

	unsigned char *m;
	mp_node *h = pool->head;
	size_t psize = (size_t)(h->end - (unsigned char *)h);
	
	int ret = posix_memalign((void **)&m, MP_ALIGNMENT, psize);
	if (ret) return NULL;

	mp_node *p, *new_node;
	new_node = (mp_node*)m;

	new_node->end = m + psize;
	new_node->next = NULL;
	new_node->failed = 0;

	m += sizeof(mp_node);
	new_node->last = m + size;
    pool->current->next = new_node;
	pool->current = new_node;

	return m;
}

static void *mp_alloc_large(mp_pool *pool, size_t size) {

	void *p = malloc(size);
	if (p == NULL) return NULL;

	size_t n = 0;
	mp_large *large;
	for (large = pool->large; large; large = large->next) {
		if (large->alloc == NULL) {
			large->alloc = p;
			return p;
		}
		if (n ++ > 3) break;
	}

	large = (mp_large *)mp_alloc(pool, sizeof(mp_large));
	if (large == NULL) {
		free(p);
		return NULL;
	}

	large->alloc = p;
	large->next = pool->large;
	pool->large = large;

	return p;
}

mp_pool *mp_create_pool(size_t size) {
    mp_pool *p = NULL;
	int ret = posix_memalign((void **)&p, MP_ALIGNMENT, size + sizeof(mp_pool) + sizeof(mp_node));
	if (ret) {
		return NULL;
	}
	
	p->max = next_power_of_two(size);
	p->current = p->head;
	p->large = NULL;

	p->head->last = (unsigned char *)p + sizeof(mp_pool) + sizeof(mp_node);
	p->head->end = p->head->last + size;

	p->head->failed = 0;
	return p;
}

void mp_destory_pool(mp_pool *pool) {
    mp_node *h, *n;
	mp_large *l;

	for (l = pool->large; l; l = l->next) {
		if (l->alloc) {
			free(l->alloc);
		}
	}

	h = pool->head->next;

	while (h) {
		n = h->next;
		free(h);
		h = n;
	}

	free(pool);
}

void *mp_alloc(mp_pool *pool, size_t size) {
    unsigned char *m;
	mp_node *p;

	if (size <= pool->max) {
		p = pool->current;

		do {
			
			m = p->last;
			if ((size_t)(p->end - m) >= size) {
				p->last = m + size + sizeof(mp_node*);
                p->failed++;
                memcpy(m, &p, sizeof(mp_node*));
				return (void*)(m + sizeof(mp_node*));
			}
			p = p->next;
		} while (p);

		return mp_alloc_block(pool, size);
	}

	return mp_alloc_large(pool, size);
}

void mp_free(mp_pool *pool, void *p) {
    mp_large *l;
	for (l = pool->large; l; l = l->next) {
		if (p == l->alloc) {
			free(l->alloc);
			l->alloc = NULL;
            return;
		}
	}

    mp_node *n;
    for(n = pool->head; n; n = n->next) {
        mp_node *tmp = (mp_node *)((unsigned char *)p - sizeof(mp_node *));
        if(tmp && tmp == (n - MP_ALIGNMENT)) {
            tmp->failed--;
            if(tmp->failed == 0) {
                tmp->last = (char*)(tmp + sizeof(mp_node));
            }
            return;
        }
    }
}

        最后测试一下：

#include <stdio.h>

int main() {
    mp_pool* mp = mp_create_pool(2048);
    char* test[5] = {0};
    for(int i = 0; i < 5; ++i) {
        test[i]  = (char*)mp_alloc(mp, 512);
        memset(test[i], 0, 512);
        strcpy(test[i], "hello world");
        
    }

    for(int i = 0; i < 5; ++i) {
        printf("%s\n", test[i]);
        mp_free(mp, (void*)test[i]);
    }

    mp_destory_pool(mp);
    return 0;
}

         编译运行看结果：

学习参考：0voice · GitHub