Linux 内存池设计构想

一、基本数据结构

 1 union m_block
 2 {
 3     union m_block*    next;
 4     unsigned int         size;
 5 };
 6 
 7 struct m_list
 8 {
 9     union m_block*     free;
10     pthread_spinlock_t    lock;
11     unsigned int            size;
12 };
13 
14 struct m_pool
15 {
16     struct m_pool*     next;
17 };
18 
19 struct m_mpcb
20 {
21     void*                    last;
22     struct m_pool*    pool;
23     pthread_spinlock_t*    lock;
24     struct m_list*        list;
25     unsigned int        available;
26 };
27         

二、内存池管理逻辑流程及结构说明

union m_block:代表一块内存,当此内存块被使用时,size成员为此内存块大小,当此内存块为空闲时候next成员指向下一块空闲内存,由此构成空闲内存链表

struct m_list:空闲内存块的管理节点,每一个节点管理一个相投大小的内存块节点,由free成员指向空闲内存块链表头结点,lock用于保护在多线程环境下对free成员的安全访问,size成员表示此内存块管理节点所管理的内存块大小

struct m_pool:实际的内存池链表,整个内存池由此构成

struct m_mpcb:内存池管理结构体,作为整个内存池的管理者,它管理由struct m_pool构成的内存池链表以及由struct m_list构成的内存块管理结构(可以是数组,搜索树等),pool成员指向内存池链表的头结点,last成员指向pool成员代表的内存池中未分配的内存起始地址,avaliable表示pool成员代表的内存池中尚未分配的可用空间。

当申请内存时,根据请求大小进行内存对齐,然后根据对齐后的大小获取对应的内存块管理节点(怎么获取下文详述),判断管理节点的free成员是否为NULL若为NULL则构造新的struct m_block结构体返回,若不为NULL则返回free成员,并更新free成员

当释放内存块时,根据给出的地址减去偏移量就能够获取内存块大小,然后根据内存块大小获取其管理节点,然后将内存块查到free链表表头并更新free成员

三、具体实现详述

1、当应用请求的内存大小区间(即:可能会请求的最大内存与可能会请求的最小内存差)较小的时候可以讲使用对齐单位(4或8)分割区间,然后每个大小对应一个struct m_list结构体,将这些结构体放在一个数组中,当需要获取管理节点时根据大小和数组首地址(存放在struct m_mpcb中的list成员)直接获取数组元素。

2、当应用请求的内存大小区间较大但是有部分比较集中例如类似4,8,3,9,34,23,16,19,512,890前面的比较集中在40以内,那么这部分可以采用第一种方法将struct m_list结构体放在一个数组中,当超出40后则可以直接通过malloc构造union m_block联合体,这种方法比较适用于大多数情况大小比较集中偶尔少数情况出现很大的 内存请求,采用这种方法时就必须在struct m_mpcb中添加最大内存块成员,当请求大小大于此值时直接适用malloc分配。

3、当应用请求内存大小区间较大,分布均匀并且申请频率均衡就可以考虑将struct m_list结构体以红黑树的形式组织,struct m_mpcb中list成员指向数的根节点,当需要分配时在树种搜索管理节点,若没有找到则创建管理节点,并添加到树中。

四、一个具体实现

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

typedef union block_t
{
    unsigned int                 size;    /**/
    union block_t*                 next;    /**/
}m_block_t;

typedef struct list_t
{
    pthread_spinlock_t            lock;    /**/
    union block_t*                 free;    /**/
}m_list_t;

typedef struct mpool
{
    struct mpool*                next;    /**/
}m_mpool;

typedef struct mpcb
{
    struct mpool*                pool;    /**/
    struct list_t*                list;    /**/
    void*                         last;    /**/
    unsigned int                 avali;    /**/
    unsigned int                maxblock;    /**/
    unsigned int                size;    /**/
    pthread_spinlock_t            lock;    /**/
}m_mpcb;

#define m_size_align(size)        (((size) + 3) & (~3))

#define m_get_offset(size)        (((size) >> 2) - 1)

#define m_get_pool()            (&memory_pool_control_block)

static struct mpcb memory_pool_control_block;

void*
m_alloc(unsigned int size)
{
    m_block_t* block = NULL;
    unsigned int as = m_size_align(size);
    if (as > m_get_pool()->maxblock) {
        block = (m_block_t*)m_salloc(sizeof(*block) + as);
    } else {
        block = m_new_block(as);
    }
    block->size = as;
    return (void*)(block + 1);
}

void
m_free(void* mem)
{
    m_block_t* block = (m_block_t*)mem - 1;
    if (block->size > m_get_pool()->maxblock) {
        free(block);
    } else {
        m_list_t* list = m_get_list(block->size);
        pthread_spin_lock(&list->lock);
        block->next = list->free;
        list->free = block;
        pthread_spin_unlock(&list->lock);
    }
}

void*
m_realloc(void* mem, unsigned int nemize)
{
    unsigned int size = ((m_block_t*)mem - 1)->size;
    if (nemize > size) {
        void* newmem = m_alloc(nemize);
        memcpy(newmem, mem, size);
        m_free(mem);
        return newmem;
    } else {
        return mem;
    }
}

int
m_mpcb_init(unsigned int maxblock, unsigned int size)
{
    unsigned int asmb = m_size_align(maxblock);
    unsigned int asp = m_size_align(size);
    m_list_t* list = m_list_init(asmb);
    m_mpool* pool = m_new_pool(asp);

    m_mpcb* mpcb = m_get_pool();
    mpcb->size = asp;
    mpcb->pool = pool;
    mpcb->list = list;
    mpcb->last = (void*)(pool + 1);
    mpcb->avali = asp;
    mpcb->maxblock = asmb;

    pthread_spin_init(&mpcb->lock, PTHREAD_PROCESS_PRIVATE);

    return 1;
}

void
m_mpcb_destroy()
{
    m_mpcb* mpcb = m_get_pool();
    m_list_destroy(mpcb->list, m_get_offset(mpcb->maxblock) + 1);

    m_pool_destroy(mpcb->pool);

    memset(mpcb, 0, sizeof(*mpcb));
}

static m_list_t*
m_list_init(unsigned int maxblock)
{
    int items = m_get_offset(maxblock) + 1;
    m_list_t* list = (m_list_t*)m_salloc(sizeof(*list) * items);
    int i = items - 1;
    for (; i >= 0; --i) {
        pthread_spin_init(&list[i].lock, PTHREAD_PROCESS_PRIVATE);
    }

    return list;
}

static m_list_t*
m_get_list(unsigned int block_size)
{
    m_list_t* list = m_get_pool()->list;
    int offset = m_get_offset(block_size);

    return (list + offset);
}

static void
m_list_destroy(m_list_t* list_head, int list_items)
{
    m_list_t* list = list_head;
    int i = list_items - 1;
    for (; i >= 0; --i) {
        pthread_spin_destroy(&list[i].lock);
    }

    free(list_head);
}

static m_block_t*
m_new_block(unsigned int size)
{
    m_list_t* list = m_get_list(size);
    pthread_spin_lock(&list->lock);

    m_block_t* block = list->free;
    if (NULL == block) {
        pthread_spin_unlock(&list->lock);
        block = (m_block_t*)m_palloc(sizeof(*block) + size);
    } else {
        list->free = block->next;
        pthread_spin_unlock(&list->lock);
    }

    return block;
}

static m_mpool*
m_new_pool(unsigned int pool_size)
{
    m_mpool* pool = (m_mpool*)m_salloc(sizeof(*pool) + pool_size);

    return pool;
}

static void
m_pool_destroy(m_mpool* pool_head)
{
    m_mpool* pool = pool_head;
    m_mpool* tmp = pool;
    while (NULL != tmp) {
        tmp = pool->next;
        free(pool);
        pool = tmp;
    }
}

static void*
m_salloc(unsigned int size)
{
    void* mem = malloc(size);
    memset(mem, 0, size);
    return mem;
}

static void*
m_palloc(unsigned int size)
{
    m_mpcb* mpcb = m_get_pool();
    pthread_spin_lock(&mpcb->lock);
    unsigned int avali = mpcb->avali;
    if (avali < size) {
        m_recover(mpcb->last, avali);
        m_mpool* npool = m_new_pool(mpcb->size);
        npool->next = mpcb->pool;
        mpcb->pool = npool;
        mpcb->avali = mpcb->size;
        mpcb->last = (void*)(npool + 1);
    }
    void* mem = mpcb->last;
    mpcb->last = (void*)((m_byte_t*)mem + size);
    mpcb->avali -= size;
    pthread_spin_unlock(&mpcb->lock);
    return mem;
}

static void
m_recover(void* mem, int offset)
{
    if (offset > sizeof(m_block_t)) {
        m_block_t* block = (m_block_t*)mem;
        block->size = offset - sizeof(m_block_t);
        m_free(block + 1);
    }
}

#undef m_get_pool

此实现是针对第二种情况实现的。

五、总结

此内存池设计可以适用不等大小内存请求。具体效率未做测试,所给demo可能无法直接通过编译,仅仅给个思路。

 

 

Linux 内存池设计构想,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。