免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 13991 | 回复: 24

young library 的轻量级内存池设计与实现 [复制链接]

论坛徽章:
0
发表于 2007-05-30 19:52 |显示全部楼层
程序库的源码下载地址: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) );
    }

论坛徽章:
0
发表于 2007-05-30 19:53 |显示全部楼层
头文件:

  1. /*
  2. * The young Library
  3. * Copyright (c) 2005 by Yang Huan(杨桓)

  4. * Permission to use, copy, modify, distribute and sell this software for any
  5. * purpose is hereby granted without fee, provided that the above copyright
  6. * notice appear in all copies and that both that copyright notice and this
  7. * permission notice appear in supporting documentation.
  8. * The author make no representations about the suitability of this software
  9. * for any purpose. It is provided "as is" without express or implied warranty.
  10. */

  11. /******************************************************************************/
  12. /******************************************************************************/
  13. #ifndef __MACRO_C_YOUNG_LIBRARY_MEMORY_FUNCTION_HEADER_FILE__
  14. #define __MACRO_C_YOUNG_LIBRARY_MEMORY_FUNCTION_HEADER_FILE__
  15. /******************************************************************************/
  16. #include "yc_definition.h"

  17. #ifdef __cplusplus
  18.     namespace youngc {  extern "C" {
  19. #endif
  20. /******************************************************************************/
  21. /******************************************************************************/

  22. /* 返回 element_size 对齐后的字节数 */
  23. size_t memalign( size_t element_size, bool memory_type );

  24. /* 获取内存池的链数 */
  25. size_t get_pool_lists_count( void );

  26. /* 获取内存池执行分配的次数 */
  27. size_t get_pool_alloc_count( void );

  28. /* 获取内存池执行归还的次数 */
  29. size_t get_pool_dealloc_count( void );

  30. /* 设置在并行系统中使用的加锁函数 */
  31. void set_pool_lock( void (*lock)(size_t index) );

  32. /* 设置在并行系统中使用的解锁函数 */
  33. void set_pool_unlock( void (*unlock)(size_t index) );

  34. /* 打印内存池 */
  35. void pool_print( void );

  36. /* 从内存池中申请至少 bytes 个字节的内存块 */
  37. void* pool_alloc( size_t bytes );

  38. /* 只将内存块回收至内存池 */
  39. void pool_dealloc( void* ptr, size_t bytes );

  40. /* 先将内存块回收至内存池,再将内存池中空闲的内存页释放 */
  41. void pool_free( void* ptr, size_t bytes );

  42. /******************************************************************************/
  43. /******************************************************************************/
  44. #ifdef __cplusplus
  45.     }  }
  46. #endif
  47. #endif
  48. /******************************************************************************/
  49. /******************************************************************************/
复制代码



实现文件:

  1. /*
  2. * The young Library
  3. * Copyright (c) 2005 by Yang Huan(杨桓)

  4. * Permission to use, copy, modify, distribute and sell this software for any
  5. * purpose is hereby granted without fee, provided that the above copyright
  6. * notice appear in all copies and that both that copyright notice and this
  7. * permission notice appear in supporting documentation.
  8. * The author make no representations about the suitability of this software
  9. * for any purpose. It is provided "as is" without express or implied warranty.
  10. */

  11. /*
  12. * 内存池由 MEMORY_POOL_LISTS 个链表组成,每个链表分别管理不同大小的内存块,
  13. * 每个链表管理的内存块大小 = MEMORY_POOL_MIN + 索引 * MEMORY_POOL_ALIGN
  14. *
  15. * 内存池原理图:
  16. * 索引:0      1     2     3           ......         MEMORY_POOL_LISTS - 1
  17. * --------------------------------------------------------------------------
  18. * | useable |     |     |     |        ......        |                     |
  19. * --------------------------------------------------------------------------
  20. * |  buffer |
  21. * -----------
  22. * |  first  |
  23. * -----------
  24. *      |
  25. *      |
  26. *      |   --------
  27. *      ->| next |--
  28. *          |------|   |
  29. *          | use  |   |
  30. *          |------|   |
  31. *          | page |   |
  32. *          --------   |
  33. *                     |
  34. *  ----------
  35. *  |
  36. *  |   --------
  37. *  ->| next | --> NULL
  38. *      |------|
  39. *      | use  | 注:使用该字的二进制位来记录内存页中各内存块的使用状态
  40. *      |------|
  41. *      | page | 注:内存页大小 = 该链表处理的内存块大小 * use的位数
  42. *      --------
  43. */

  44. /******************************************************************************/
  45. /******************************************************************************/
  46. #include <stdio.h>
  47. #include <stdlib.h>
  48. #include "yc_memory.h"

  49. #ifdef __cplusplus
  50.     namespace youngc {  extern "C" {
  51. #endif
  52. /******************************************************************************/
  53. /******************************************************************************/

  54. enum YOUNG_LIBRARY_MEMORY_CONSTANT
  55. {
  56.     MEMORY_ALIGN_SIZE = sizeof(int),
  57.     MEMORY_POOL_BUFFER = 8,
  58.     MEMORY_POOL_ALIGN = 4,
  59.     MEMORY_POOL_MIN = 8,
  60.     MEMORY_POOL_MAX = 128,
  61.     MEMORY_POOL_BLOCKS = sizeof(ylib_word_t) * BYTE_BITS,
  62.     MEMORY_POOL_LISTS = ( MEMORY_POOL_MAX - MEMORY_POOL_MIN )
  63.                         / MEMORY_POOL_ALIGN + 1
  64. };

  65. typedef struct memory_page
  66. {
  67.     ylib_word_t          use;  /* 二进制位映射的内存块已使用则该位为1,否则为0 */
  68.     struct memory_page*  next; /* 下一个内存页 */
  69. } mempage_t;

  70. typedef struct memory_list
  71. {
  72.     size_t      useable;                    /* 未满的可供分配的内存页数 */
  73.     mempage_t*  buffer[MEMORY_POOL_BUFFER]; /* 页面缓存 */
  74.     mempage_t*  first;                      /* 第一个内存页 */
  75. } memlist_t;

  76. #define  MEMALLOC( bytes)  malloc( bytes )

  77. #define  MEMFREE( ptr )    free( ptr )

  78. #define  LIST_INDEX( bytes ) \
  79.          ( (bytes) <= MEMORY_POOL_MIN ? 0 \
  80.            : ((bytes) - MEMORY_POOL_MIN + MEMORY_POOL_ALIGN - 1) \
  81.              / MEMORY_POOL_ALIGN )

  82. #define  BLOCK_SIZE( index )  ( MEMORY_POOL_MIN + (index) * MEMORY_POOL_ALIGN )

  83. #define  PAGE_SIZE( index )  ( BLOCK_SIZE(index) * MEMORY_POOL_BLOCKS )

  84. /******************************************************************************/
  85. /******************************************************************************/

  86. static void (*pool_lock)( size_t ) = NULL;
  87. static void (*pool_unlock)( size_t ) = NULL;
  88. static size_t pool_alloc_count = 0;
  89. static size_t pool_dealloc_count = 0;
  90. static memlist_t pool[MEMORY_POOL_LISTS] = { {0, {NULL}, NULL} };

  91. static unsigned char bitmap[] =
  92. {
  93.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  94.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
  95.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  96.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
  97.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  98.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
  99.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  100.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
  101.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  102.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
  103.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  104.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
  105.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  106.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
  107.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
  108.     0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  109. };

  110. /******************************************************************************/
  111. /******************************************************************************/

  112. size_t get_pool_lists_count( void )
  113. {
  114.     return MEMORY_POOL_LISTS;
  115. }

  116. size_t get_pool_alloc_count( void )
  117. {
  118.     return pool_alloc_count;
  119. }

  120. size_t get_pool_dealloc_count( void )
  121. {
  122.     return pool_dealloc_count;
  123. }

  124. void set_pool_lock( void (*lock)(size_t) )
  125. {
  126.     pool_lock = lock;
  127. }

  128. void set_pool_unlock( void (*unlock)(size_t) )
  129. {
  130.     pool_unlock = unlock;
  131. }

  132. /******************************************************************************/

  133. size_t memalign( size_t element_size, bool memory_type )
  134. {
  135.     size_t residue = MEMORY_ALIGN_SIZE - 1;
  136.     size_t alignsize = element_size & ~residue;

  137.     if( element_size & residue )
  138.         alignsize += MEMORY_ALIGN_SIZE;

  139.     if( memory_type == true && alignsize < sizeof(ylib_inner_t) )
  140.         alignsize = sizeof(ylib_inner_t);

  141.     return alignsize;
  142. }

  143. /******************************************************************************/

  144. void pool_print( void )
  145. {
  146.     int i, j;
  147.     mempage_t* curr;
  148.     ylib_word_t mask;
  149.     char *str_last, bits[MEMORY_POOL_BLOCKS + 1] = { '\0' };

  150.     for( i = 0; i < MEMORY_POOL_LISTS; ++i )
  151.     {
  152.         if( !(pool[i].first) )
  153.             continue;

  154.         printf( "\npool[%d] chunk = %d", i, BLOCK_SIZE(i) );
  155.         printf( "\n\tpool[%d].useable = %u", i, pool[i].useable );
  156.         for( j = 0; j < MEMORY_POOL_BUFFER; ++j )
  157.             printf( "\n\tpool[%d].buffer[%d] = %p", i, j, pool[i].buffer[j] );
  158.         printf( "\n\tpool[%d].first = %p: ", i, pool[i].first );

  159.         curr = pool[i].first;

  160.         while( curr )
  161.         {
  162.             mask = 1;
  163.             str_last = bits + MEMORY_POOL_BLOCKS;
  164.             for( j = 0; j < MEMORY_POOL_BLOCKS; ++j, mask <<= 1 )
  165.                 *--str_last = (char)(curr->use & mask ? '1' : '0');
  166.             printf( "\n\t" );
  167.             printf( "next = %p | use = %s", curr->next, bits );
  168.             curr = curr->next;
  169.         }
  170.     }
  171. }

  172. /******************************************************************************/

  173. static void* page_alloc( size_t index, mempage_t* curr )
  174. {
  175.     void* ptr = NULL;
  176.     size_t i;

  177.     /* 先找到第一个空闲块所在的字节 */
  178.     for( i = 0; i < sizeof(ylib_word_t); ++i )
  179.     {
  180.         ylib_byte_t value = (ylib_byte_t)( curr->use >> (BYTE_BITS * i) );

  181.         if( value != YLIB_BYTE_MAX )
  182.         {
  183.             ylib_word_t mask = 1;
  184.             size_t biti = bitmap[value]; /* 从映射表中查找第一个等于 0 的位 */
  185.             mask <<= ( BYTE_BITS * i + biti ); /* 计算掩码 */
  186.             curr->use |= mask; /* 设置使用标志 */
  187.             ptr = (ylib_byte_t*)curr + sizeof(mempage_t)
  188.                   + (i * BYTE_BITS + biti) * BLOCK_SIZE( index );
  189.             if( curr->use == YLIB_WORD_MAX )
  190.                 --( pool[index].useable );
  191.             return ptr;
  192.         } /* end if */
  193.     } /* end for i */

  194.     return ptr;
  195. }

  196. /******************************************************************************/

  197. void* pool_alloc( size_t bytes )
  198. {
  199.     void* ptr = NULL;

  200.     if( bytes > MEMORY_POOL_MAX )
  201.     {
  202.         ptr = MEMALLOC( bytes );
  203.     }
  204.     else
  205.     {
  206.         int i;
  207.         mempage_t* pg = NULL;
  208.         size_t index = LIST_INDEX( bytes );

  209.         if( pool_lock )
  210.             pool_lock( index );

  211.         if( pool[index].first && pool[index].useable > 0 )
  212.         {
  213.             mempage_t *prev = NULL, *curr = NULL;

  214.             /* 先查找页面缓存 */
  215.             for( i = 0; i < MEMORY_POOL_BUFFER; ++i )
  216.             {
  217.                 if( pool[index].buffer[i] )
  218.                 {
  219.                     ptr = page_alloc( index, pool[index].buffer[i] );

  220.                     /* 如果该页已满,则将该页自页面缓存中退出 */
  221.                     if( pool[index].buffer[i]->use == YLIB_WORD_MAX )
  222.                         pool[index].buffer[i] = NULL;
  223.                     else if( i > 0 )
  224.                     {
  225.                         /* 如果该页不在缓存首,则将该页调整至缓存首 */
  226.                         pool[index].buffer[0] = pool[index].buffer[i];
  227.                         pool[index].buffer[i] = NULL;
  228.                     }

  229.                     goto EXIT_POOL_ALLOC;
  230.                 }
  231.             } /* 页面缓存 */

  232.             /* 页面缓存为空,则遍历链中的所有内存页寻找空闲的内存块 */
  233.             curr = pool[index].first;
  234.             while( curr )
  235.             {
  236.                 if( curr->use == YLIB_WORD_MAX ) /* 该页中没有空闲块 */
  237.                 {
  238.                     /* 进入下一页 */
  239.                     prev = curr;
  240.                     curr = curr->next;
  241.                 }
  242.                 else /* 该页中有空闲块 */
  243.                 {
  244.                     size_t count = 0;
  245.                     ptr = page_alloc( index, curr );

  246.                     /* 继续遍历链表,寻找其他未满的页面,将之放入页面缓存 */
  247.                     while( curr && count < pool[index].useable )
  248.                     {
  249.                         if( curr->use != YLIB_WORD_MAX )
  250.                         {
  251.                             /* 页面缓存还有位置则放入页面缓存 */
  252.                             if( count < MEMORY_POOL_BUFFER )
  253.                                 pool[index].buffer[count] = curr;

  254.                             ++count;

  255.                             /* 如果当前页未满并且不在链首,则将之移至链首 */
  256.                             if( pool[index].first != curr )
  257.                             {
  258.                                 prev->next = curr->next;
  259.                                 curr->next = pool[index].first;
  260.                                 pool[index].first = curr;
  261.                                 curr = prev->next;
  262.                                 continue;
  263.                             }
  264.                         }
  265.                         prev = curr;
  266.                         curr = curr->next;
  267.                     }

  268.                     goto EXIT_POOL_ALLOC;
  269.                 } /* end else */
  270.             } /* end while */
  271.         } /* end if */
  272.         else
  273.         {
  274.             /* 该链下未分配内存页或无空闲块,此时需增加新的内存页 */
  275.             pg = (mempage_t*)MEMALLOC( sizeof(mempage_t) + PAGE_SIZE(index) );
  276.             if( pg )
  277.             {
  278.                 pg->next = pool[index].first;
  279.                 pool[index].first = pg;
  280.                 pg->use = 1;
  281.                 ptr = (ylib_byte_t*)pg + sizeof(mempage_t);
  282.                 ++( pool[index].useable );
  283.                 pool[index].buffer[0] = pg;
  284.             }
  285.         }

  286. EXIT_POOL_ALLOC:
  287.         if( pool_unlock )
  288.             pool_unlock( index );
  289.     } /* end else */

  290.     if( ptr )
  291.         ++pool_alloc_count;

  292.     return ptr;
  293. }

  294. /******************************************************************************/

  295. void pool_dealloc( void* ptr, size_t bytes )
  296. {
  297.     if( !ptr )
  298.         return;

  299.     if( bytes <= MEMORY_POOL_MAX )
  300.     {
  301.         size_t index = LIST_INDEX( bytes );
  302.         size_t pagesize = PAGE_SIZE( index );
  303.         mempage_t *prev = NULL, *curr = pool[index].first;
  304.         ylib_byte_t *begin, *end, *blk = (ylib_byte_t*)ptr;

  305.         if( pool_lock )
  306.             pool_lock( index );

  307.         while( curr )
  308.         {
  309.             begin = (ylib_byte_t*)curr + sizeof(mempage_t);
  310.             end = begin + pagesize;
  311.             if( blk < begin || blk >= end ) /* 判断ptr是否在当前页内 */
  312.             {
  313.                 prev = curr;
  314.                 curr = curr->next;
  315.             }
  316.             else
  317.             {
  318.                 size_t blk_size = BLOCK_SIZE( index );

  319.                 /* 检查ptr是否正确 */
  320.                 if( (blk - begin) % blk_size == 0 )
  321.                 {
  322.                     ylib_word_t mask = 1;
  323.                     size_t blk_index = (blk - begin) / blk_size;
  324.                     size_t old = curr->use;
  325.                     mask <<= blk_index;
  326.                     curr->use &= ~mask;

  327.                     /* 如果当前页不在链首,则将之移至链首 */
  328.                     if( pool[index].first != curr )
  329.                     {
  330.                         prev->next = curr->next;
  331.                         curr->next = pool[index].first;
  332.                         pool[index].first = curr;
  333.                     }

  334.                     /* 如果归还前内存页已满,则将可用页数加一 */
  335.                     if( old == YLIB_WORD_MAX )
  336.                         ++( pool[index].useable );

  337.                     ++pool_dealloc_count;
  338.                 }
  339.                 break;
  340.             } /* end else */
  341.         } /* end while */

  342.         if( pool_unlock )
  343.             pool_unlock( index );

  344.         return;
  345.     } /* end if */

  346.     /* ptr不是由内存池分配 */
  347.     MEMFREE( ptr );
  348.     ++pool_dealloc_count;
  349. }

  350. /******************************************************************************/

  351. void pool_free( void* ptr, size_t bytes )
  352. {
  353.     if( ptr )
  354.         pool_dealloc( ptr, bytes );

  355.     if( bytes <= MEMORY_POOL_MAX )
  356.     {
  357.         int i;
  358.         size_t index = LIST_INDEX( bytes );
  359.         mempage_t *erase = NULL, *prev = NULL, *curr = pool[index].first;

  360.         if( pool_lock )
  361.             pool_lock( index );

  362.         while( curr )
  363.         {
  364.             if( curr->use != 0 ) /* 判断是否是空闲页 */
  365.             {
  366.                 prev = curr;
  367.                 curr = curr->next;
  368.             }
  369.             else
  370.             {
  371.                 /* 从页面缓存中退出 */
  372.                 for( i = 0; i < MEMORY_POOL_BUFFER; ++i )
  373.                 {
  374.                     if( pool[index].buffer[i] == curr )
  375.                     {
  376.                         pool[index].buffer[i] = NULL;
  377.                         break;
  378.                     }
  379.                 }

  380.                 if( prev )
  381.                     prev->next = curr->next; /* 空闲页不在链首 */
  382.                 else
  383.                     pool[index].first = curr->next; /* 空闲页在链首 */

  384.                 /* 将空闲页释放 */
  385.                 erase = curr;
  386.                 curr = curr->next;
  387.                 MEMFREE( erase );
  388.                 --( pool[index].useable );
  389.             } /* end if */
  390.         } /* end while */

  391.         if( pool_unlock )
  392.             pool_unlock( index );
  393.     }
  394. }

  395. /******************************************************************************/
  396. /******************************************************************************/
  397. #ifdef __cplusplus
  398.     }  }
  399. #endif
  400. /******************************************************************************/
  401. /******************************************************************************/
复制代码

论坛徽章:
0
发表于 2007-05-30 19:59 |显示全部楼层
我正在写一个类似的库,有空多交流!

论坛徽章:
0
发表于 2007-05-30 20:02 |显示全部楼层
你给出你测试程序.
说明比直接CALL malloc的优点(时间,空间的).

然后和其它班主商量,看可精华与否.

论坛徽章:
0
发表于 2007-05-30 20:18 |显示全部楼层
测试是整个程序库测试程序的一部分,不好单独提出来。

论坛徽章:
0
发表于 2007-05-30 20:56 |显示全部楼层
有点类似SLAB.
工作量不小.
你这个主要用在什么地方?

原帖由 phoneix 于 2007-5-30 20:18 发表
测试是整个程序库测试程序的一部分,不好单独提出来。

论坛徽章:
0
发表于 2007-05-30 22:56 |显示全部楼层
顶楼主一个~
我现在做的东西也涉及到了内存池,由于只用在我自己的特殊场合,所以也没怎么刻意的封装,数据结构用的是拉链式哈希表~

论坛徽章:
0
发表于 2007-05-30 23:05 |显示全部楼层
本来是不打算写的,内存池原本不在程序库的设计计划中的,开始是想让使用程序库的程序员自己提供的,
后来发现没有多少人去写,就只好自己写一个了。因为是以简单和可移植来作为设计原则的,理论上在有
操作系统的软件平台,编译器又支持C标准库的动态内存实现,内存池可以直接使用。如果不满足以上条件
的话可以把 MEMALLOC 和 MEMFREE 换成自定义的系统内存分配和释放函数即可使用。使用场合没有
什么特殊的要求。

[ 本帖最后由 phoneix 于 2007-5-30 23:12 编辑 ]

论坛徽章:
0
发表于 2007-05-31 08:47 |显示全部楼层
你是什么程序库需要这个?

原帖由 phoneix 于 2007-5-30 23:05 发表
本来是不打算写的,内存池原本不在程序库的设计计划中的,开始是想让使用程序库的程序员自己提供的,
后来发现没有多少人去写,就只好自己写一个了。因为是以简单和可移植来作为设计原则的,理论上在有
操作系统 ...

论坛徽章:
0
发表于 2007-05-31 09:28 |显示全部楼层
原帖由 思一克 于 2007-5-31 08:47 发表
你是什么程序库需要这个?



类STL的算法容器库
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP