程序库的源码下载地址：http://gforge.osdn.net.cn/frs/?group_id=86
本篇介绍程序库中的内存池算法。
内存池函数的声明文件为: young/youngc/yc_memory.h
内存池函数的实现文件为: young/youngc/yc_memory.c
**3.1**
首先来看一下内存池算法用到的一些类型和常量。
下面的类型和常量定义在头文件 yc_definition.h 内；
硬件字节类型 ：ylib_byte_t;
硬件机器字类型 ：ylib_word_t;
一个字节所占用的二进制位数 ：BYTE_BITS；
字节类型的最大值 ：YLIB_BYTE_MAX；
字类型的最大值 ：YLIB_WORD_MAX；
下面的类型和常量定义在实现文件 yc_memory.c 内；
内存页类型：
typedef struct memory_page
{
struct memory_page* next;
ylib_word_t use;
} mempage_t;
内存链类型：
typedef struct memory_list
{
size_t useable;
mempage_t* buffer[MEMORY_POOL_BUFFER];
mempage_t* first;
} memlist_t;
内存池每个链的字节对齐数 ：MEMORY_POOL_ALIGN；
内存池每个链的缓存页数：MEMORY_POOL_BUFFER；
内存池管理的最小字节数 ：MEMORY_POOL_MIN_BYTES；
内存池管理的最大字节数 ：MEMORY_POOL_MAX_BYTES；
每个内存页包含的内存块数 ：MEMORY_POOL_BLOCKS；
内存池包含的内存链数 ：MEMORY_POOL_LISTS。
**3.2**
内存池原理图：
索引：0 1 2 3 ...... MEMORY_POOL_LISTS - 1
--------------------------------------------------------------------------
| useable | | | | ...... | |
--------------------------------------------------------------------------
| buffer |
-----------
| first |
-----------
|
|
| --------
－＞| next |－－
|------| |
| use | |
|------| |
| page | |
-------- |
|
－－－－－－－－－－
|
| --------
－＞| next | －－＞ NULL
|------|
| use |
|------|
| page |
--------
实际上，内存池的全称应该是小内存块内存池，内存池管理的内存块的上限是
MEMORY_POOL_MAX_BYTES 个字节，超过这个数值的申请要求会被转调用至 malloc 函数，
正因为此，所以在释放内存的时候必须显示地指定要释放的内存块的大小，这样才能确保
正确地释放。
内存池是一个 memlist_t 指针类型的数组，数组的大小为 MEMORY_POOL_LISTS 数组内
的每个指针元素指向一条内存链，每个内存链由大小不同的内存页以单向链表的形式组成。
为了方便管理，凡是向内存池申请小于等于 MEMORY_POOL_MAX_BYTES 个字节的内存块都会
被自动调整为 MEMORY_POOL_ALIGN 的倍数，而每个内存链则管理着不同大小的内存块，可
用该公式计算：内存链管理的内存块大小 ＝ MEMORY_POOL_MIN + 索引 * MEMORY_POOL_ALIGN。
由于每个内存链管理的内存块都很小，为了减少向系统申请内存的次数和内存碎片，内
存链的每个节点并不是内存块，而是一种比内存块大的多的被称为内存页的数据结构。内存
页分由三部分组成：
1、use 是一个管理内存页中的内存块分配状态的机器字，该字的每一位对应一个内存
块，换言之，每个内存页中包含的内存块的总数就是该字的总位数；
2、next 是一个指向下一个内存页的指针；
3、内存页中用以分配内存块的缓存区，缓存大小 = 该链表管理的内存块大小 × use的位数。
**3.2**
分配功能的实现。
内存功能功能由函数 pool_alloc 实现，其声明如下：
void* pool_alloc( size_t bytes )；
函数的参数是申请的动态内存字节数，返回值为一个指向动态内存首地址的空指针，
如果分配失败，返回的值为 NULL。
如前所述，内存池处理的内存块大小是有上限的，当申请的字节数大于阈值的时候，则
直接调用标准库中的 malloc 函数，只有当申请的字节数小于等于阈值的时候才会使用内存
池进行分配，这个阈值就是前面提到的 MEMORY_POOL_MAX_BYTES，默认值为128。
为了便于分配，内存池不一定会刚好分配用户申请的那么大的内存，而是会对申请的
值进行一些调整。内存池不会分配小于 MEMORY_POOL_MIN_BYTES 的内存块，算法会将分配
的字节数调整至刚好不小于申请的字节数的 MEMORY_POOL_ALIGN 的倍数，默认管理的最小
内存块是8字节，对齐的字节数为4字节。举几个例子：假设用户申请的是4个字节，由于小
于最小内存块的8字节，算法自动将申请的字节数调整为8；再假设用户申请的是14个字节，
由于14不是4的倍数，算法自动将申请的字节数调整为刚好大于14的4的倍数，也就是16。
在完成了字节对齐后，就可以确定由哪个内存链来进行分配，确定内存链后，先进入
该链的页面缓存，在页面缓存中寻找是否有可供使用的内存页。链的页面缓存是长度等于
MEMORY_POOL_BUFFER 的一个 mempage_t* 数组，对数组进行遍历，寻找第一个不等于 NULL
的值，这个值就是需要的内存页指针。需要注意的是，被分配的内存页是连在 mempage_t
下面的，所以在查找内存块时，需要对指针进行偏移操作，跳过 sizeof(mempage_t) 个字
节。
在找到了内存页后，进入页面分配函数 page_alloc，该函数负责从内存页中分配内存
块。前面提到过，使用内存页中 use 成员的二进制位来记录内存分配的状态，因此，查找
可被分配的内存块实际上就是查找 use 中等于 0 的第一个二进制位。很显然最直接的方法
就是对 use 的二进制位从前至后进行遍历，直到遇到第一个等于 0 的二进制位为止。但是
这种方法的效率实在太差，内存池使用了查表算法进行优化。一个 ylib_word_t 是由 N 个
字节组成的，因此先遍历 use 中的字节，如果其值等于 YLIB_BYTE_MAX ，则表示这个字节
已被分配完，因为只有当字节的所有位均为 1 时才会等于这个值；不等于 YLIB_BYTE_MAX
则表示该字节所映射的内存块还有空闲的，可以被分配。在确定了所在的字节后，便可以用
查表法快速的确定该字节第一个等于 0 的二进制位了。在 yc_memory.c 中有一个名为 bitmap
的数组，将字节所表示的整数值作为索引映射至数组，得到的返回值即为第一个等于 0 的
二进制位索引。后面的工作就简单了，根据字节索引和位索引计算出所映射的内存块地址，
通过掩码做位或运算将该位置 1，返回前再次判断一下 use 的值是否等于 YLIB_WORD_MAX,
以确定内存页是否已满，如果已满，则需将内存链的 useable 成员减一，同时将该页自页
面缓存中退出，最后将内存块地址返回给用户。
但是缓存并不总是会有内存页的，当缓存为空时，就需要对链表进行遍历，以找到可用
的内存页。对链表的遍历并不是找到第一个可分配的内存页后就停止，这样做会让后面的分
配在不久之后又必须要遍历链表，来一趟不容易，不如来了以后多做点事，免得以后老是要
跑来爬楼梯。所以内存池的链表遍历实际上是一个整理操作，它会在遍历的过程中动态调整
链表的排列，把找到的可供分配的内存页逐一上调到链表的首位，这样遍历完成后，所有的
可分配内存页都被上调至了链表的前部，在调整的同时用找到的未满内存页重新填充页面缓
存。这里需要注意的是遍历的页面数，其实并不需要将链表这个遍历，在遍历的同时，用一
个无负号整数 count 记录遍历过的未满内存页，当 count == useable 的时候，表示后面已
经没有可供分配的内存页了，此时就可退出循环。
以上的行为均在 useable 大于 0 的时候发生，而当 useable 等于 0 的时候，既不需
要遍历页面缓存，也不需要遍历链表，只需直接调用底层动态内存分配函数 MEMALLOC 分配
一个内存页，将 use 赋值为 1，将分配的内存页挂在内存链的首位，同时放入页面缓存，最
后返回内存页的第一个内存块即可。
**3.3**
归还功能的实现。
归还实际上分为两个操作，一个是归还，一个是释放。
归还操作由函数 pool_dealloc 实现，其声明如下：
void pool_dealloc( void* ptr, size_t bytes )；
函数的第一个参数是指向要归还的内存块的指针，第二个参数是要归还的内存块的大小。
进入函数后，先判断指针是否为空，接着判断内存块的大小，如果大于内存池所能管理
的最大内存块，则直接调用 MEMFREE 将之释放；如果小于等于则有可能是由内存池分配出去
的。注意，只是有可能而已。
根据内存块的大小，先计算出内存块理论上所属的内存链，然后对该内存链进行遍历，
在遍历内存页的过程中，判断内存块的地址是否落在内存页的首地址和末地址之间，如果是
的话，则表示找到了内存块所属的内存页，如果没有，则继续遍历，如果遍历至链尾依然没
有找到，则表示该内存块不是由内存池分配的，直接调用 MEMFREE 将之释放。
在确定了内存块所属的内存页后，依然不能马上执行归还操作，还必须确定内存块的地
址是否正确。由于分配时，是以 BLOCK_SIZE(index) 来进行对齐的，所以归还时的地址也必
须能满足这个对齐要求，亦即满足条件：(块地址 - 页首地址) % BLOCK_SIZE(index) == 0，
验证无误后，方能执行归还操作。
归还的操作很简单，只需要将该 use 中映射至该内存块的二进制位置 0 即可。随后将
内存页调整至链首，这样做一来可以方便下次归还，二来可以方便当页面缓存使用完后，对
链表的快速遍历。
归还操作只是把归还的内存块重新放进内存池，并不会把空闲的内存页释放给系统。假
如应用程序申请了大量的内存而后又将之归还给了内存池，此时内存池的使用率接近 0%，而
其他的应用程序却因为大量内存被内存池占用而无法正常运行，此时需要将内存池占用的大
量空闲内存释放给系统以供其他应用程序使用。很显然，归还操作并不能胜任，这个工作必
须由释放操作来完成。
释放操作由函数 pool_free 实现，其声明如下：
void pool_free( void* ptr, size_t bytes )；
函数的第一个参数是指向要归还的内存块的指针，第二个参数是要归还的内存块的大小。
释放操作分为两步，第一步直接调用 pool_dealloc 完成内存块的归还，第二步遍历整
个链表，在遍历的过程中将空闲的内存页释放给系统。注意，第一个参数是可以为 NULL 的，
此时，将跳过第一步，直接执行第二步。
为什么在释放操作里是对整个链表的遍历呢？因为我预期大部分的时候执行的都会是归
还操作，只有当系统内存紧张的时候才需要执行释放操作，此时释放操作执行一次即可满足
要求，接下来就又可以执行归还操作了。譬如，可以调用 get_pool_dealloc_count 函数了
解执行了归还的次数，当达到某个阈值的时候就可以调用 pool_free 释放一些空闲的内存页。
**3.4**
并发控制。
在多线程环境下，内存池的操作将会因线程之间的切换而崩溃！为此，内存池在实现的
时候提供了并行加锁和解锁操作。为了移植，加锁和解锁的实现交由用户来实现，内存池只
负责调度。
设置加锁函数：void set_pool_lock( void (*lock)(size_t index) )。
设置解锁函数：void set_pool_unlock( void (*unlock)(size_t index) )。
两个函数的参数都是一个声明原型如 void f(size_t) 的函数指针。这里解释一下传递
进来的加锁和解锁函数为什么需要一个 size_t index 参数。这个 index 参数就是内存链的
索引值，仔细观察一下就会发现，实际上每个内存链是相互独立的，内存池最多可以允许
MEMORY_POOL_LISTS 个在不同的链表内的线程同时操作。通过 index 这个参数，实现加锁和
解锁功能的用户就可以对不同的链表分别进行加锁和解锁。例如在 Windows 系统下，可以先
调用 get_pool_lists_count 函数以获取内存链的总数，然后创建一个互斥量数组,数组的大
小就等于内存链的总数，在实现的加锁和解锁函数里可以根据 index 参数决定是对哪个互斥
量进行操作。
**3.5**
模板化。
在 C++ 中使用内存池可以借助模板来进行一下包装。STL 中的内存分配器已经为我们
提供了一个样本。
模板化的内存池源码在 young/youngcpp/ycpp_memory.hpp 中。下面只列出三个主要的
成员函数。
pointer allocate( size_type n )
{
return (pointer)( youngc::pool_alloc( sizeof(T) * n ) );
}
void deallocate( pointer ptr, size_type n )
{
youngc::pool_dealloc( ptr, sizeof(T) * n );
}
~pool_allocator()
{
youngc::pool_free( NULL, sizeof(T) );
}
phoneix 回复于：2007-05-30 19:53:58
头文件：
/*
* The young Library
* Copyright (c) 2005 by Yang Huan(杨桓)
* Permission to use, copy, modify, distribute and sell this software for any
* purpose is hereby granted without fee, provided that the above copyright
* notice appear in all copies and that both that copyright notice and this
* permission notice appear in supporting documentation.
* The author make no representations about the suitability of this software
* for any purpose. It is provided "as is" without express or implied warranty.
*/
/******************************************************************************/
/******************************************************************************/
#ifndef __MACRO_C_YOUNG_LIBRARY_MEMORY_FUNCTION_HEADER_FILE__
#define __MACRO_C_YOUNG_LIBRARY_MEMORY_FUNCTION_HEADER_FILE__
/******************************************************************************/
#include "yc_definition.h"
#ifdef __cplusplus
namespace youngc { extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/
/* 返回 element_size 对齐后的字节数 */
size_t memalign( size_t element_size, bool memory_type );
/* 获取内存池的链数 */
size_t get_pool_lists_count( void );
/* 获取内存池执行分配的次数 */
size_t get_pool_alloc_count( void );
/* 获取内存池执行归还的次数 */
size_t get_pool_dealloc_count( void );
/* 设置在并行系统中使用的加锁函数 */
void set_pool_lock( void (*lock)(size_t index) );
/* 设置在并行系统中使用的解锁函数 */
void set_pool_unlock( void (*unlock)(size_t index) );
/* 打印内存池 */
void pool_print( void );
/* 从内存池中申请至少 bytes 个字节的内存块 */
void* pool_alloc( size_t bytes );
/* 只将内存块回收至内存池 */
void pool_dealloc( void* ptr, size_t bytes );
/* 先将内存块回收至内存池，再将内存池中空闲的内存页释放 */
void pool_free( void* ptr, size_t bytes );
/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
} }
#endif
#endif
/******************************************************************************/
/******************************************************************************/
实现文件：
/*
* The young Library
* Copyright (c) 2005 by Yang Huan(杨桓)
* Permission to use, copy, modify, distribute and sell this software for any
* purpose is hereby granted without fee, provided that the above copyright
* notice appear in all copies and that both that copyright notice and this
* permission notice appear in supporting documentation.
* The author make no representations about the suitability of this software
* for any purpose. It is provided "as is" without express or implied warranty.
*/
/*
* 内存池由 MEMORY_POOL_LISTS 个链表组成，每个链表分别管理不同大小的内存块，
* 每个链表管理的内存块大小 = MEMORY_POOL_MIN + 索引 * MEMORY_POOL_ALIGN
*
* 内存池原理图：
* 索引：0 1 2 3 ...... MEMORY_POOL_LISTS - 1
* --------------------------------------------------------------------------
* | useable | | | | ...... | |
* --------------------------------------------------------------------------
* | buffer |
* -----------
* | first |
* -----------
* |
* |
* | --------
* －＞| next |－－
* |------| |
* | use | |
* |------| |
* | page | |
* -------- |
* |
* －－－－－－－－－－
* |
* | --------
* －＞| next | －－＞ NULL
* |------|
* | use | 注：使用该字的二进制位来记录内存页中各内存块的使用状态
* |------|
* | page | 注：内存页大小 = 该链表处理的内存块大小 * use的位数
* --------
*/
/******************************************************************************/
/******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "yc_memory.h"
#ifdef __cplusplus
namespace youngc { extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/
enum YOUNG_LIBRARY_MEMORY_CONSTANT
{
MEMORY_ALIGN_SIZE = sizeof(int),
MEMORY_POOL_BUFFER = 8,
MEMORY_POOL_ALIGN = 4,
MEMORY_POOL_MIN = 8,
MEMORY_POOL_MAX = 128,
MEMORY_POOL_BLOCKS = sizeof(ylib_word_t) * BYTE_BITS,
MEMORY_POOL_LISTS = ( MEMORY_POOL_MAX - MEMORY_POOL_MIN )
/ MEMORY_POOL_ALIGN + 1
};
typedef struct memory_page
{
ylib_word_t use; /* 二进制位映射的内存块已使用则该位为1，否则为0 */
struct memory_page* next; /* 下一个内存页 */
} mempage_t;
typedef struct memory_list
{
size_t useable; /* 未满的可供分配的内存页数 */
mempage_t* buffer[MEMORY_POOL_BUFFER]; /* 页面缓存 */
mempage_t* first; /* 第一个内存页 */
} memlist_t;
#define MEMALLOC( bytes) malloc( bytes )
#define MEMFREE( ptr ) free( ptr )
#define LIST_INDEX( bytes ) \
( (bytes) <= MEMORY_POOL_MIN ? 0 \
: ((bytes) - MEMORY_POOL_MIN + MEMORY_POOL_ALIGN - 1) \
/ MEMORY_POOL_ALIGN )
#define BLOCK_SIZE( index ) ( MEMORY_POOL_MIN + (index) * MEMORY_POOL_ALIGN )
#define PAGE_SIZE( index ) ( BLOCK_SIZE(index) * MEMORY_POOL_BLOCKS )
/******************************************************************************/
/******************************************************************************/
static void (*pool_lock)( size_t ) = NULL;
static void (*pool_unlock)( size_t ) = NULL;
static size_t pool_alloc_count = 0;
static size_t pool_dealloc_count = 0;
static memlist_t pool[MEMORY_POOL_LISTS] = { {0, {NULL}, NULL} };
static unsigned char bitmap[] =
{
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
/******************************************************************************/
/******************************************************************************/
size_t get_pool_lists_count( void )
{
return MEMORY_POOL_LISTS;
}
size_t get_pool_alloc_count( void )
{
return pool_alloc_count;
}
size_t get_pool_dealloc_count( void )
{
return pool_dealloc_count;
}
void set_pool_lock( void (*lock)(size_t) )
{
pool_lock = lock;
}
void set_pool_unlock( void (*unlock)(size_t) )
{
pool_unlock = unlock;
}
/******************************************************************************/
size_t memalign( size_t element_size, bool memory_type )
{
size_t residue = MEMORY_ALIGN_SIZE - 1;
size_t alignsize = element_size & ~residue;
if( element_size & residue )
alignsize += MEMORY_ALIGN_SIZE;
if( memory_type == true && alignsize < sizeof(ylib_inner_t) )
alignsize = sizeof(ylib_inner_t);
return alignsize;
}
/******************************************************************************/
void pool_print( void )
{
int i, j;
mempage_t* curr;
ylib_word_t mask;
char *str_last, bits[MEMORY_POOL_BLOCKS + 1] = { '\0' };
for( i = 0; i < MEMORY_POOL_LISTS; ++i )
{
if( !(pool.first) )
continue;
printf( "\npool[%d] chunk = %d", i, BLOCK_SIZE(i) );
printf( "\n\tpool[%d].useable = %u", i, pool.useable );
for( j = 0; j < MEMORY_POOL_BUFFER; ++j )
printf( "\n\tpool[%d].buffer[%d] = %p", i, j, pool.buffer[j] );
printf( "\n\tpool[%d].first = %p: ", i, pool.first );
curr = pool.first;
while( curr )
{
mask = 1;
str_last = bits + MEMORY_POOL_BLOCKS;
for( j = 0; j < MEMORY_POOL_BLOCKS; ++j, mask <<= 1 )
*--str_last = (char)(curr->use & mask ? '1' : '0');
printf( "\n\t" );
printf( "next = %p | use = %s", curr->next, bits );
curr = curr->next;
}
}
}
/******************************************************************************/
static void* page_alloc( size_t index, mempage_t* curr )
{
void* ptr = NULL;
size_t i;
/* 先找到第一个空闲块所在的字节 */
for( i = 0; i < sizeof(ylib_word_t); ++i )
{
ylib_byte_t value = (ylib_byte_t)( curr->use >> (BYTE_BITS * i) );
if( value != YLIB_BYTE_MAX )
{
ylib_word_t mask = 1;
size_t biti = bitmap[value]; /* 从映射表中查找第一个等于 0 的位 */
mask <<= ( BYTE_BITS * i + biti ); /* 计算掩码 */
curr->use |= mask; /* 设置使用标志 */
ptr = (ylib_byte_t*)curr + sizeof(mempage_t)
+ (i * BYTE_BITS + biti) * BLOCK_SIZE( index );
if( curr->use == YLIB_WORD_MAX )
--( pool[index].useable );
return ptr;
} /* end if */
} /* end for i */
return ptr;
}
/******************************************************************************/
void* pool_alloc( size_t bytes )
{
void* ptr = NULL;
if( bytes > MEMORY_POOL_MAX )
{
ptr = MEMALLOC( bytes );
}
else
{
int i;
mempage_t* pg = NULL;
size_t index = LIST_INDEX( bytes );
if( pool_lock )
pool_lock( index );
if( pool[index].first && pool[index].useable > 0 )
{
mempage_t *prev = NULL, *curr = NULL;
/* 先查找页面缓存 */
for( i = 0; i < MEMORY_POOL_BUFFER; ++i )
{
if( pool[index].buffer )
{
ptr = page_alloc( index, pool[index].buffer );
/* 如果该页已满，则将该页自页面缓存中退出 */
if( pool[index].buffer->use == YLIB_WORD_MAX )
pool[index].buffer = NULL;
else if( i > 0 )
{
/* 如果该页不在缓存首，则将该页调整至缓存首 */
pool[index].buffer[0] = pool[index].buffer;
pool[index].buffer = NULL;
}
goto EXIT_POOL_ALLOC;
}
} /* 页面缓存 */
/* 页面缓存为空，则遍历链中的所有内存页寻找空闲的内存块 */
curr = pool[index].first;
while( curr )
{
if( curr->use == YLIB_WORD_MAX ) /* 该页中没有空闲块 */
{
/* 进入下一页 */
prev = curr;
curr = curr->next;
}
else /* 该页中有空闲块 */
{
size_t count = 0;
ptr = page_alloc( index, curr );
/* 继续遍历链表，寻找其他未满的页面，将之放入页面缓存 */
while( curr && count < pool[index].useable )
{
if( curr->use != YLIB_WORD_MAX )
{
/* 页面缓存还有位置则放入页面缓存 */
if( count < MEMORY_POOL_BUFFER )
pool[index].buffer[count] = curr;
++count;
/* 如果当前页未满并且不在链首，则将之移至链首 */
if( pool[index].first != curr )
{
prev->next = curr->next;
curr->next = pool[index].first;
pool[index].first = curr;
curr = prev->next;
continue;
}
}
prev = curr;
curr = curr->next;
}
goto EXIT_POOL_ALLOC;
} /* end else */
} /* end while */
} /* end if */
else
{
/* 该链下未分配内存页或无空闲块，此时需增加新的内存页 */
pg = (mempage_t*)MEMALLOC( sizeof(mempage_t) + PAGE_SIZE(index) );
if( pg )
{
pg->next = pool[index].first;
pool[index].first = pg;
pg->use = 1;
ptr = (ylib_byte_t*)pg + sizeof(mempage_t);
++( pool[index].useable );
pool[index].buffer[0] = pg;
}
}
EXIT_POOL_ALLOC:
if( pool_unlock )
pool_unlock( index );
} /* end else */
if( ptr )
++pool_alloc_count;
return ptr;
}
/******************************************************************************/
void pool_dealloc( void* ptr, size_t bytes )
{
if( !ptr )
return;
if( bytes <= MEMORY_POOL_MAX )
{
size_t index = LIST_INDEX( bytes );
size_t pagesize = PAGE_SIZE( index );
mempage_t *prev = NULL, *curr = pool[index].first;
ylib_byte_t *begin, *end, *blk = (ylib_byte_t*)ptr;
if( pool_lock )
pool_lock( index );
while( curr )
{
begin = (ylib_byte_t*)curr + sizeof(mempage_t);
end = begin + pagesize;
if( blk < begin || blk >= end ) /* 判断ptr是否在当前页内 */
{
prev = curr;
curr = curr->next;
}
else
{
size_t blk_size = BLOCK_SIZE( index );
/* 检查ptr是否正确 */
if( (blk - begin) % blk_size == 0 )
{
ylib_word_t mask = 1;
size_t blk_index = (blk - begin) / blk_size;
size_t old = curr->use;
mask <<= blk_index;
curr->use &= ~mask;
/* 如果当前页不在链首，则将之移至链首 */
if( pool[index].first != curr )
{
prev->next = curr->next;
curr->next = pool[index].first;
pool[index].first = curr;
}
/* 如果归还前内存页已满，则将可用页数加一 */
if( old == YLIB_WORD_MAX )
++( pool[index].useable );
++pool_dealloc_count;
}
break;
} /* end else */
} /* end while */
if( pool_unlock )
pool_unlock( index );
return;
} /* end if */
/* ptr不是由内存池分配 */
MEMFREE( ptr );
++pool_dealloc_count;
}
/******************************************************************************/
void pool_free( void* ptr, size_t bytes )
{
if( ptr )
pool_dealloc( ptr, bytes );
if( bytes <= MEMORY_POOL_MAX )
{
int i;
size_t index = LIST_INDEX( bytes );
mempage_t *erase = NULL, *prev = NULL, *curr = pool[index].first;
if( pool_lock )
pool_lock( index );
while( curr )
{
if( curr->use != 0 ) /* 判断是否是空闲页 */
{
prev = curr;
curr = curr->next;
}
else
{
/* 从页面缓存中退出 */
for( i = 0; i < MEMORY_POOL_BUFFER; ++i )
{
if( pool[index].buffer == curr )
{
pool[index].buffer = NULL;
break;
}
}
if( prev )
prev->next = curr->next; /* 空闲页不在链首 */
else
pool[index].first = curr->next; /* 空闲页在链首 */
/* 将空闲页释放 */
erase = curr;
curr = curr->next;
MEMFREE( erase );
--( pool[index].useable );
} /* end if */
} /* end while */
if( pool_unlock )
pool_unlock( index );
}
}
/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
} }
#endif
/******************************************************************************/
/******************************************************************************/
converse 回复于：2007-05-30 19:59:50
我正在写一个类似的库,有空多交流!
思一克 回复于：2007-05-30 20:02:03
你给出你测试程序.
说明比直接CALL malloc的优点(时间,空间的).
然后和其它班主商量,看可精华与否.
phoneix 回复于：2007-05-30 20:18:04
测试是整个程序库测试程序的一部分，不好单独提出来。
思一克 回复于：2007-05-30 20:56:12
有点类似SLAB.
工作量不小.
你这个主要用在什么地方?
引用：原帖由 phoneix 于 2007-5-30 20:18 发表
测试是整个程序库测试程序的一部分，不好单独提出来。
cugb_cat 回复于：2007-05-30 22:56:35
顶楼主一个～
我现在做的东西也涉及到了内存池，由于只用在我自己的特殊场合，所以也没怎么刻意的封装，数据结构用的是拉链式哈希表～
phoneix 回复于：2007-05-30 23:05:57
本来是不打算写的，内存池原本不在程序库的设计计划中的，开始是想让使用程序库的程序员自己提供的，
后来发现没有多少人去写，就只好自己写一个了。因为是以简单和可移植来作为设计原则的，理论上在有
操作系统的软件平台，编译器又支持C标准库的动态内存实现，内存池可以直接使用。如果不满足以上条件
的话可以把 MEMALLOC 和 MEMFREE 换成自定义的系统内存分配和释放函数即可使用。使用场合没有
什么特殊的要求。
[ 本帖最后由 phoneix 于 2007-5-30 23:12 编辑 ]
思一克 回复于：2007-05-31 08:47:04
你是什么程序库需要这个？
引用：原帖由 phoneix 于 2007-5-30 23:05 发表
本来是不打算写的，内存池原本不在程序库的设计计划中的，开始是想让使用程序库的程序员自己提供的，
后来发现没有多少人去写，就只好自己写一个了。因为是以简单和可移植来作为设计原则的，理论上在有
操作系统 ...
converse 回复于：2007-05-31 09:28:02
引用：原帖由 思一克 于 2007-5-31 08:47 发表
你是什么程序库需要这个？
类STL的算法容器库
nully 回复于：2007-05-31 18:00:05
强烈想知道比malloc快多少
phoneix 回复于：2007-05-31 20:20:19
这个我没有测试过，在不同的平台下结果不一样，对我来讲没有什么意义。我写这个内存池主要的一个目的是在嵌入式系统开发时使用，在嵌入式系统下很多都不支持malloc和free，如果有了这个内存池，那么只需要在底层实现最简单的分配和释放算法就可以达到一个比较理想的使用效果了。
wuxiangzhi 回复于：2007-05-31 20:30:56
这个稍做修改可用来共享内存区的管理。
思一克 回复于：2007-05-31 20:44:35
一般的程序不需要这种"内存池". 嵌入系统上应该比较有用, 如LZ说的没有malloc, free.
适合的地方是程序有同时并行大量申请释放小memory的情况. 符合这情况的时候很少.
正常的程序调用malloc就可以了.
mik 回复于：2007-05-31 20:49:09
和 malloc() 工作原理不同，所以与 malloc() 不具可比性。
wuxiangzhi 回复于：2007-05-31 20:55:31
呵呵，现在用到的共享内存池的动态管理，和这个类似。
benjiam 回复于：2007-06-02 01:04:13
这个例子和 apache 的分配方式很相近的.
你可疑去读读apache 的lib 源码. 基本思想差不多. 但别人是按照4k 为一个page 进行分配的 你已字节进行分配.实在...... apache 的每个耶还有个头信息. 很巧妙的.
phoneix 回复于：2007-06-02 12:55:16
你说的我在设计的时候都考虑过了，apache 主要是在服务器上使用的，系统资源很丰富，可是在嵌入式系统上就不是这样了，8位、16位机的寻址空间有多大，算过吗？动不动就4K，哪里受得了？为什么我叫它轻量级的内存池呢？就是因为主要的使用对象是嵌入式系统，在服务器上一般都有更完善的、更安全的内存池可以使用，这也是一开始我就没打算实现内存池的原因。
MackedNice 回复于：2007-06-07 13:16:42
呵呵。。。。
lz的程序库由更新了么？？
写了这么牛的东东出来。。
benlan 回复于：2007-06-07 13:25:11
能否加个内存泄露检测上去，也许在嵌入式里更用的上
原理是：
分配时把 adress和size记下来，放到一个hash等进去
free的时候，把此地址从hash里拿掉
然后在查看有无泄露时，使用dump类的函数把现在所有未free的address dump出来
加个宏，控制是否release 版本时把检测去了。
phoneix 回复于：2007-06-09 09:44:46
引用：原帖由 benlan 于 2007-6-7 13:25 发表
能否加个内存泄露检测上去，也许在嵌入式里更用的上
原理是：
分配时把 adress和size记下来，放到一个hash等进去
free的时候，把此地址从hash里拿掉
然后在查看有无泄露时，使用dump类的函数把现在所有未fre ...
当时写了个 pool_print 就是想调试的时候用的，在 test_dblnklst.c 测试程序有它的使用方法，可以输出整个内存池的状态。实际上，
由于使用的是位映射的方式，所以直接判断位映射字是否等于 0 就可以知道是否有内存泄露了。不过功能毕竟太过简单了，我会在后面加上dump 函数的，谢谢你的建议。
unixpm 回复于：2007-06-09 12:52:02
大家可以看看csdn的一期杂志叫调试还是测试，里面有jjhou和周伟明的两篇文章，一个就是详细讲内存池包括和malloc函数的比较，还有一篇就是讲解内存泄漏检测的
antonym55 回复于：2007-06-09 15:37:02
引用：原帖由 phoneix 于 2007-5-31 20:20 发表
这个我没有测试过，在不同的平台下结果不一样，对我来讲没有什么意义。我写这个内存池主要的一个目的是在嵌入式系统开发时使用，在嵌入式系统下很多都不支持malloc和free，如果有了这个内存池，那么只需要在底层实 ...
不知针对的什么嵌入式系统? 现在很少有不支持malloc 和free的，
以前在学校学单片机时写的一大堆汇编代码，现在用C51只用很少的代码就可以实现，
而且结构比较清晰，唉，我上学里怎么没碰上这种好事.
phoneix 回复于：2007-06-09 19:01:21
51其实没有必要，本身寻址空间就那么大一点，直接在程序里划一块数组更简单一些，但是DSP、ARM这些比较流行的嵌入式平台可能就用的上了。
benlan 回复于：2007-06-10 16:54:58
引用：原帖由 phoneix 于 2007-6-9 09:44 发表
当时写了个 pool_print 就是想调试的时候用的，在 test_dblnklst.c 测试程序有它的使用方法，可以输出整个内存池的状态。实际上，
由于使用的是位映射的方式，所以直接判断位映射字是否等于 0 就可以知道是 ...
漏说了一点，就是在malloc的时候，把 __function__ __line__ 传进来的，然后在dump时，会dump出function和line，这样子查起来就比较能直接定位到哪里泄露了。
|
