/*
编译器为64位系统，指针占8字节，int占4字节
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#define MP_ALIGNMENT 32
#define MP_PAGE_SIZE 4096
#define MP_MAX_ALLOC_FROM_POOL (MP_PAGE_SIZE-1)
// 内存对齐，以 alignmen 为单位，如：17->20, 30->32
#define mp_align(n, alignment) (((n)+(alignment-1)) & ~(alignment-1))
#define mp_align_ptr(p, alignment) (void *)((((size_t)p)+(alignment-1)) & ~(alignment-1))
//大块内存
typedef struct mp_large_s
{
struct mp_large_s *next;//指向大块内存链表的下一个大块内存
void *alloc;//指向实际分配的大块内存
}mp_large_t;
//内存池节点：小块内存
typedef struct mp_node_s
{
unsigned char *last;//指向内存池节点已分配的末尾地址，下一次内存分配的起始地址
unsigned char *end;//指向内存池节点的末尾地址
struct mp_node_s *next;//指向下一个内存池节点
size_t failed;//当前内存块分配空间失败的次数
}mp_node_t;
//内存池
typedef struct mp_pool_s
{
size_t max;//小块内存能分配的最大空间，超过该值使用大块内存分配
mp_node_t *current;//指向当前内存池
struct mp_large_s *large;//指向大块内存链表
mp_node_t head[0];//指向小块内存链表
}mp_pool_t;
static void *mp_alloc_large(mp_pool_t *pool, size_t size);
//创建内存池
mp_pool_t *mp_create_pool(size_t size)
{
mp_pool_t *p;
//int *a;
//printf("sizeof(a) is %d\n",sizeof(a));
/*申请空间
参数：首地址，对齐方式，大小，malloc无法分配4K空间
空间大小：申请的空间+内存池管理信息+内存池节点
posix_memalign() returns zero on success, or one of the error values
listed in the next section on failure. The value of errno is not set. On
Linux (and other systems), posix_memalign() does not modify memptr on
failure. A requirement standardizing this behavior was added in
POSIX.1-2016.
调用posix_memalign( )成功时会返回size字节的动态内存，并且这块内存的地址是alignment的倍数。
参数alignment必须是2的幂，还是void指针的大小的倍数。返回的内存块的地址放在了memptr里面，函数返回值是0.
*/
// printf("sizeof(int) is %d\n",sizeof(int));
// printf("sizeof(unsigned int) is %d\n",sizeof(unsigned int));
// printf("sizeof(size_t) is %d\n",sizeof(size_t));
// printf("sizeof(p)、sizeof(max)、sizeof(current)、sizeof(large) sizeof(head) is %d,%d,%d,%d,%d\n",sizeof(p),sizeof(p->max),sizeof(p->current),sizeof(p->large),sizeof(p->head));
// printf("sizeof(mp_pool_t)、sizeof(mp_node_t) is %d,%d\n",sizeof(mp_pool_t),sizeof(mp_node_t));
int ret = posix_memalign((void **)&p,MP_ALIGNMENT,size+sizeof(mp_pool_t)+sizeof(mp_node_t));//4096+24+32
if(ret != 0)
{
return NULL;
}
//设置小块内存能分配的最大空间
printf("size is %d\n",size);
p->max = (size<MP_MAX_ALLOC_FROM_POOL) ? size:MP_MAX_ALLOC_FROM_POOL;//最小块内存不超过4KB
//设置当前内存池的节点
p->current = p->head;
//设置大块内存链表
p->large = NULL;
//设置内存池节点信息
p->head->last = (unsigned char *)p+sizeof(mp_pool_t)+sizeof(mp_node_t);
p->head->end = p->head->last+size;
p->head->failed = 0;
return p;
}
void mp_destory_pool(mp_pool_t *pool)
{
mp_node_t *h,*n;
struct mp_large_s *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_reset_pool(mp_pool_t *pool)
{
mp_node_t *h;
struct mp_large_s *l;
//释放大块内存
for(l=pool->large;l;l=l->next)
{
if(l->alloc)
{
free(l->alloc);
}
}
pool->large = NULL;
//重置小块内存，并不调用free将内存交还给系统，只是指针的复位操作
for(h=pool->head;h;h=h->next)
{
h->last = (unsigned char *)h+sizeof(mp_node_t);
}
}
// 小块内存分配
static void *mp_alloc_block(mp_pool_t *pool, size_t size)
{
unsigned char *m;
mp_node_t *p, *new_node, *current;
mp_node_t *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;
}
// 初始化内存块
new_node = (mp_node_t*)m;
new_node->end = m + psize;
new_node->next = NULL;
new_node->failed = 0;
// 将指针m移动到可分配内存的开始位置
m += sizeof(mp_node_t);
// 对指针做内存对齐
m = mp_align_ptr(m, MP_ALIGNMENT);
// 设置新内存块的last
new_node->last = m + size;
// 当前指向的内存池结点（该结点及后面结点都可分配内存，前面结点无法分配）
current = pool->current;
// 寻找最后一个链表结点，结点的查找从 current 开始，不需要每次从头开始查找
for (p = current; p->next; p = p->next)
{
// 每次调用mp_alloc_block函数，代表之前所有小块内存空间分配失败
// 此时，所有小块内存的 failed+1，表示不满足用户的需求 +1 次
// 若某个小块内存若连续 5 次都不满足用户需求，则跳过这个小块内存，下次不再遍历它
// 由于链表结点的插入是尾插法，所以先插入的结点内存分配失败次数多
if (p->failed++ > 4)
{
current = p->next; // 调整 current 指向下一个内存块
}
}
// 将新创建的内存块，尾插到小块内存链表
p->next = new_node;
// 更新pool->current指针，判断 current 是否为空？
// 若非空，指向current指向的结点；若为空，代表之前所有的内存块都分配失败，则指向新的内存块
pool->current = current ? current : new_node;
return m;
}
// 内存分配
void *mp_alloc(mp_pool_t *pool, size_t size)
{
unsigned char *m;
mp_node_t *p;
// 1、用户申请的是小块内存
if(size <= pool->max)
{
// 指向第一个要遍历的内存池结点
p = pool->current;
// 遍历小块内存链表，寻找可用的空间分配内存
do{
// 指针内存对齐
m = mp_align_ptr(p->last, MP_ALIGNMENT);
// 当前结点的剩余空间足够分配
if ((size_t)(p->end - m) >= size)
{
// 更新last指针
p->last = m + size;
return m;
}
// 若当前内存块的剩余内存小于所需内存，则到下一个内存块中寻找
p = p->next;
}while (p);
// 没找到合适的小块内存，则创建一个新的小块内存
return mp_alloc_block(pool, size);
}
// 2、用户申请的是大块内存
return mp_alloc_large(pool, size);
}
// 分配大块内存
static void *mp_alloc_large(mp_pool_t *pool, size_t size)
{
// 调用 malloc 申请大块内存
void *p = malloc(size);
if (p == NULL)
{
return NULL;
}
size_t n = 0;
struct mp_large_s *large;
// 遍历大块内存链表，找到可以挂载 p 的位置
for (large = pool->large; large; large = large->next)
{
// 找到可以挂载的地方
if (large->alloc == NULL)
{
large->alloc = p;
return p;
}
// 若连续 4 次都没找到，就不再寻找了
if (n ++ > 3) break;
}
// 创建一个新的大块内存结点，用来挂载p
large = mp_alloc(pool, sizeof(struct mp_large_s));
if (large == NULL)
{
free(p);
return NULL;
}
// 将新创建的结点，头插到大块内存链表中
large->alloc = p;
large->next = pool->large;
pool->large = large;
return p;
}
// void *mp_memalign(mp_pool_t *pool, size_t size, size_t alignment)
// {
// void *p;
// int ret = posix_memalign(&p, alignment, size);
// if (ret)
// {
// return NULL;
// }
// struct mp_large_s *large = mp_alloc(pool, sizeof(struct mp_large_s));
// if (large == NULL)
// {
// free(p);
// return NULL;
// }
// large->alloc = p;
// large->next = pool->large;
// pool->large = large;
// return p;
// }
// void *mp_nalloc(mp_pool_t *pool, size_t size)
// {
// unsigned char *m;
// mp_node_t *p;
// if (size <= pool->max)
// {
// p = pool->current;
// do{
// m = p->last;
// if ((size_t)(p->end - m) >= size)
// {
// p->last = m+size;
// return m;
// }
// p = p->next;
// }while (p);
// return mp_alloc_block(pool, size);
// }
// return mp_alloc_large(pool, size);
// }
void *mp_calloc(mp_pool_t *pool, size_t size)
{
void *p = NULL;
p = mp_alloc(pool, size);
if (p)
{
memset(p, 0, size);
}
return p;
}
// 内存池释放，只针对大块内存
void mp_free(mp_pool_t *pool, void *p)
{
struct mp_large_s *l;
//遍历大块内存块
for (l = pool->large; l; l = l->next)
{
if (p == l->alloc)
{
free(l->alloc);
l->alloc = NULL;
return ;
}
}
}
int main(int argc, char *argv[])
{
int size = 1 << 12;//4096
mp_pool_t *p = mp_create_pool(size);
int i = 0;
// for (i = 0; i < 10; i++)
// {
// void *mp = mp_alloc(p, 512);
// // mp_free(mp);
// }
// printf("mp_create_pool: %ld\n", p->max);
printf("mp_align(123, 32): %d, mp_align(17, 32): %d\n", mp_align(24, 32), mp_align(17, 32));
// printf("mp_align_ptr(p->current, 32): %lx, p->current: %lx, mp_align(p->large, 32): %lx, p->large: %lx\n", mp_align_ptr(p->current, 32), p->current, mp_align_ptr(p->large, 32), p->large);
// int j = 0;
// for (i = 0; i < 5; i++)
// {
// char *pp = mp_calloc(p, 32);
// for (j = 0;j < 32;j ++)
// {
// if (pp[j] != 0)
// {
// printf("calloc wrong\n");
// }
// printf("calloc success\n");
// }
// }
//printf("mp_reset_pool\n");
for (i = 0;i < 5;i ++)
{
void *l = mp_alloc(p, 8192);
if(l != NULL)
{
mp_free(p, l);
printf("l is not NULL\n");
}
else
{
printf("l is NULL\n");
}
}
mp_reset_pool(p);
//printf("mp_destory_pool\n");
for (i = 0;i < 58;i ++)
{
mp_alloc(p, 256);
}
mp_destory_pool(p);
return 0;
}