发个简单（易用）的内存池

本帖最后由 duanjigang 于 2010-06-01 10:45 编辑

cme_mem_20100601.tar.gz (5.92 KB)

cme_mem_20100201.tar.gz (2 KB)
修改历史：
2010-02-01:
首先是把节点中的list和ptr改成 head 和tail了，为了方便理解，老炮给的意见
另外是，在节点中添加了一个raw_data指针，跟data在初始化时同时指向数据内存地址，这样做的目的是防止
用户在退出时忘记了free每一个node,如果采用以前的方式，整个内存池也就忘记Free了，虽然能够在退出时提示开发者，
修改后，能够在提示开发者的基础上释放未被释放的节点。
2010-06-01;
修改内容：其一，初始化N个节点时，为了保留栈的地址，须预留一个节点，因此最多只能申请到N-1个，做了修改，我们在实际开辟时申请N+1个，这样对用户就透明了。其二：new_mem_node时。需要把当前栈顶的节点的data置空，当时写错了，搞成了栈底节点的data置空，虽然不影响功能，但逻辑错误，做了修改。

######################################################################
简单技术含量不高还敢说，易用就看各位的反响了

，期待更好的改进建议。
自己根据实际工作需要写的，主要是为了省事，稍微提高点效率，省下了N多数组的声明和调用。
把多个类型的内存节点集合到一起统一管理，初始化时统一初始化,调用如下:

init_mem_list (TYPE_S1, sizeof(s1_t), 100);
init_mem_list (TYPE_S2, sizeof(s2_t), 200);

复制代码

退出时统一释放,调用如下:

clean_mem_list();

复制代码

运行过程中调用
调用封装的new和free函数

extern u_int8_t * new_mem_node(u_int8_t type);
extern void free_mem_node( u_int8_t * addr);

复制代码

个人感觉还是比较方便的,效率相对还比较高，首先根据类型哈希到对应的链表上，然后每个链表就是一个栈，弹栈或者压栈就是new和Free操作。

一个简单的使用例子如下:

//cme_hook.c

#include <linux/module.h>
#include <linux/kernel.h>
#include "head.h"
#include "mem_pool.c"

typedef struct
{
u_int16_t key1;
u_int32_t key2;
}s1_t;
typedef struct
{
u_int8_t key1;
u_int16_t key2;
}s2_t;
const u_int8_t TYPE_S1 = 1;
const u_int8_t TYPE_S2 = 2;

s1_t* s1_list[20];
s2_t* s2_list[50];

int init(void)
{
int i = 0;
init_mem_list (TYPE_S1, sizeof(s1_t), 100);
init_mem_list (TYPE_S2, sizeof(s2_t), 200);

for (i = 0; i < 20; i++)
{
      s1_list[i] = (s1_t*)new_mem_node(TYPE_S1);
      s1_list[i]->key1 = 2*i;
      s1_list[i]->key2 = 2*i+1;
}

for (i = 0; i < 50; i++)
{
      s2_list[i] = (s2_t*)new_mem_node(TYPE_S2);
      s2_list[i]->key1 = 3*i;
      s2_list[i]->key2 = 3*i+1;
}

for (i = 0; i < 20; i++)
{
      printk("s1_list[%d]=<%u, %u>\n", i, s1_list[i]->key1, s1_list[i]->key2);
}

for (i = 0; i < 50; i++)
{
      printk("s2_list[%d]=<%u, %u>\n", i, s2_list[i]->key1, s2_list[i]->key2);
}

   printk("cme hook registering.......\n");
   return 0;
}

void finish(void)
{
int i = 0;

for (i = 0; i < 20; i++) free_mem_node(((u_int8_t*)s1_list[i]));
for (i = 0; i < 50; i++) free_mem_node(((u_int8_t*)s2_list[i]));
clean_mem_list();
   printk("removing cme hook.......\n");
}

module_init(init)
module_exit(finish)
MODULE_LICENSE("GPL");
MODULE_VERSION("1.0");

附件是例子完整代码以及这个小小内存池的实现代码，大家多多提意见改进。

#######################################
附件看不到，贴下mem_pool.c中的实现代码

//mem_pool.c
#include <linux/module.h>
#include <linux/kernel.h>
#include "head.h"
int print_msg = 0;

#define MAX_MEM_LIST 256
typedef struct _node
{
u_int8_t * data;
struct _node * next;
struct _node * pre;
}mem_node_t;
typedef struct
{
mem_node_t * list;
mem_node_t * ptr;
spinlock_t lock;
u_int8_t    type;
u_int8_t    valid;
}mem_list_t;
static mem_list_t mem_list[MAX_MEM_LIST];
static int init_all_mem_list(void)
{
int i = 0;

for (i = 0; i < MAX_MEM_LIST; i++)
{
      mem_list[i].list = NULL;
      mem_list[i].ptr = NULL;
      mem_list[i].type = 0;
      mem_list[i].valid = 0;
}
return 1;
}
static int mem_list_init = 0;
u_int8_t * new_mem_node(u_int8_t type)
{
u_int8_t * prt = NULL;
mem_node_t * plist = mem_list[type].list;
if(!plist) return NULL;

spin_lock(&mem_list[type].lock);

if(mem_list[type].ptr != mem_list[type].list)
{
      prt = (u_int8_t*)(mem_list[type].ptr->data + 1);
      if(print_msg) printk("alloc one node:%p\n", prt);
      plist->data = NULL;
      mem_list[type].ptr = mem_list[type].ptr->pre;
}else
{

      if(print_msg) printk("no node for alloc\n");
}
spin_unlock(&mem_list[type].lock);
return prt;
}
void free_mem_node( u_int8_t * addr)
{

u_int8_t type = *(addr - 1);
mem_list_t * plist = &mem_list[type];

spin_lock(&plist->lock);

if(plist->ptr->next && addr)
{
      if(print_msg) printk("free one mem node %p of type:%u\n", addr, type);
      plist->ptr = plist->ptr->next;
      plist->ptr->data = (u_int8_t*)(addr-1);
}else
{
      if(print_msg) printk("free  node error\n");
}
spin_unlock(&plist->lock);

}

int init_mem_list ( u_int8_t type, int size, int length)
{
int i = 0;
mem_list_t * plist = &mem_list[i];

if (!mem_list_init)
{
      init_all_mem_list();
      mem_list_init = 1;
}

if ((type == 0)||(size <= 0) || (length <= 0)) return 0;

plist = &mem_list[type];

if(plist->valid) return 1;
plist->valid = 1;
spin_lock_init(&plist->lock);
plist->type = type;

for ( i = 0; i < length; i++ )
{
      u_int8_t * ptype = 0;
      mem_node_t * p = (mem_node_t*)malloc(sizeof(mem_node_t));

      if(!p)goto err;

      p->data = malloc(size + sizeof(u_int8_t));

      if(!p->data)
      {
         free(p);
         goto err;
      }
      ptype = p->data;
      *ptype = type;
      //p->type = type;

      p->next = NULL;
      p->pre = NULL;
      if(!plist->list)
      {
         plist->list = p;
         plist->ptr = p;
         continue;
      }

      p->next = plist->list->next;
      plist->list->next = p;
      p->pre = plist->list;
      if(p->next) p->next->pre = p;
}
while(plist->ptr->next) plist->ptr = plist->ptr->next;
plist->valid = 1;
if(print_msg) printk("init %d  nodes of type %u success\n", length, type);
return 1;
err:
while(plist->list)
{
      mem_node_t * p = plist->list;
      plist->list = plist->list->next;
      if(p)
      {
         if(p->data) free(p->data);
         free(p);
      }
}
mem_list[type].valid = 0;
mem_list[type].type = 0;
mem_list[type].list = NULL;
mem_list[type].ptr = NULL;
return 0;
}

void clean_mem_list(void)
{

int num = 0;
int left = -1;
int i = 0;
u_int8_t type;

for (i = 0; i < MAX_MEM_LIST; i++)
{
      mem_list_t * plist = &mem_list[i];
      if ( !plist->valid ) continue;
      plist->valid = 0;
      type = plist->type;
      num = 0;
      while(plist->list)
      {
         mem_node_t * p = plist->list;
         if(p == plist->ptr) left = 0;

         plist->list = plist->list->next;
         if(p)
         {
            num++;
            if(left >= 0) left++;
            if(p->data) free(p->data);
            free(p);
         }
      }

      if(print_msg)
      printk("free %d mem node(s) of type %u success, %d node(s) being used now\n",
         num, type, left - 1);
}
}

头文件head.h

#ifndef _HEAD_H_
#define _HEAD_H_

#ifdef __KERNEL__
#define malloc(a) kmalloc(a,GFP_ATOMIC)
#define free(a) kfree(a)
#endif
extern u_int8_t * new_mem_node(u_int8_t type);
extern void free_mem_node( u_int8_t * addr);
extern int init_mem_list ( u_int8_t type, int size, int length);
extern void clean_mem_list(void);
#endif

目前没有在运行过程中做动态的reallocate,也就是说new失败时，就需要淘汰已有节点，主动free了

整个的存储图示意图如下：
[ 本帖最后由 duanjigang 于 2010-1-13 10:55 编辑 ]

mem_list.PNG (8.85 KB)

作者: duanjigang 发布时间: 2010-01-11

free做了个统一接口，因为类型存在了数据的前一个位置

作者: duanjigang 发布时间: 2010-01-11

多谢段兄的好文啊。现在好像看不了附件

作者: Godbach 发布时间: 2010-01-11

QUOTE:

原帖由 Godbach 于 2010-1-11 22:42 发表
多谢段兄的好文啊。现在好像看不了附件

附件正在审核，奇怪了，再来一次看看

cme_mem.tar.gz (6.5 KB)

作者: duanjigang 发布时间: 2010-01-11

最近严打呢好像

作者: platinum 发布时间: 2010-01-11

我看到的附件都是审核中谢谢分享
不过我记得好像sourceforge有个不错的内存池的^_^

作者: ubuntuer 发布时间: 2010-01-11

最近附件有点问题，好像是这周末能恢复。

作者: scutan 发布时间: 2010-01-12

附件中的实现文件贴出来了

作者: duanjigang 发布时间: 2010-01-12

借这个贴子问一下
段兄为何使用 spin_lock 而不是 spin_lock_bh，什么情况下应该加 _bh 什么时候应该不加呢？

作者: platinum 发布时间: 2010-01-12

QUOTE:

原帖由 platinum 于 2010-1-12 09:49 发表
借这个贴子问一下
段兄为何使用 spin_lock 而不是 spin_lock_bh，什么情况下应该加 _bh 什么时候应该不加呢？

呵呵，白金兄这个问题还没有解决啊。

作者: Godbach 发布时间: 2010-01-12

QUOTE:

原帖由 Godbach 于 2010-1-12 10:07 发表

呵呵，白金兄这个问题还没有解决啊。

是呀，一直很迷茫，小伟能不能帮我解释一下

作者: platinum 发布时间: 2010-01-12

QUOTE:

原帖由 platinum 于 2010-1-12 10:14 发表

是呀，一直很迷茫，小伟能不能帮我解释一下

很惭愧的说，我也不是很清楚。前段时间还特意为这个问题翻了一下LKD2等相关的书籍。只看到了底半和顶半的区别及应用的场合，感觉看的还是不很明白

作者: Godbach 发布时间: 2010-01-12

QUOTE:

原帖由 platinum 于 2010-1-12 09:49 发表
借这个贴子问一下
段兄为何使用 spin_lock 而不是 spin_lock_bh，什么情况下应该加 _bh 什么时候应该不加呢？

在LDD上翻出来看了看：
spin_lock_bh disables software interrupts
before taking the lock, but leaves hardware interrupts enabled.
spin_lock_bh通常用在进程中，用来禁止抢断和禁止软中断，所以个人感觉这就跟试用场景有关了
如果你的代码lock和unlock之间访问的资源不会被一个中断处理访问的话，应该就不需要考虑禁止软中断了吧。
那样就直接试用spin_lock,如果代码片段很可能在中断处理中执行或者与中断处理的程序访问同一资源，
就应该调用spin_lock_irq或者spin_lock_bh吧
我的理解大概是这样，再看看别的文章

[ 本帖最后由 duanjigang 于 2010-1-12 13:30 编辑 ]

作者: duanjigang 发布时间: 2010-01-12

QUOTE:

原帖由 platinum 于 2010-1-12 10:14 发表

是呀，一直很迷茫，小伟能不能帮我解释一下

对了，你的应用场景是什么？？这些API的区别是什么我没仔细研究过，就用过read_lock,write_lock
还有就是这个spin_lock,也没怎么求甚解，借这个机会，大家正好讨论下

作者: duanjigang 发布时间: 2010-01-12

我的应用场景很简单，写基于 netfilter 的 hook 模块，通过 netlink 与 userspace 交互
在内核态工作时，有三个地方需要用到 lock 机制
1、收取 netlink 信令并插入链表
2、hook 中处理数据包时查找链表
3、timer 中 destroy 函数中有删除链表的操作
为了安全起见，我都是用的是 _bh，不知道是不是没必要，段兄这块是怎么做的？

至于 rwlock、spinlock，我一般都是用 spinlock，只有在很多读，很少写的时候才使用 rwlock
但是我看文章说在极大读，极小写的时候可以改用 RCU 锁，但 RCU 的应用场景很复杂，很多种情形，很多种用法，一头雾水……

另一个问题，对于一个 spin_lock 变量，能否在不同地方使用不同的锁
比如

fun1()
{
spin_lock(&lock);
do_something();
spin_unlock(&lock);
}

fun2()
{
spin_lock_bh(&lock);
do_something();
spin_unlock_bh(&lock);
}
同一个锁，一个地方有 _bh，另一个没有？是不是这也和应用场景有关，看是否需要对 local 进行 disable ？

[ 本帖最后由 platinum 于 2010-1-12 13:51 编辑 ]

作者: platinum 发布时间: 2010-01-12

我们也有类似的应用。前两种都用了_bh

作者: Godbach 发布时间: 2010-01-12

QUOTE:

原帖由 platinum 于 2010-1-12 13:44 发表
我的应用场景很简单，写基于 netfilter 的 hook 模块，通过 netlink 与 userspace 交互
在内核态工作时，有三个地方需要用到 lock 机制
1、收取 netlink 信令并插入链表
2、hook 中处理数据包时查找链表
3、 ...

netfilter的hook点是在softirq的上下文中,参考以下文章，我觉得你的用法至少是足够了，而没有欠缺,如果要采取更确切的
锁操作api, 觉得netlink和timer中的锁操作应该参考下文再分析下（还是结合场景

）

   至于同一个spin_lock,个人觉得应该可以支持不同的操作，禁softirq或者不禁softirq都行，关键是你要保证lock和unlock的
操作类型是匹配的，也就是说bh_lock了，就要bh_unlock.当然，最好试验下，感觉不顶事。

   白金兄有没有在netlink通讯中遇到用户态Sendmsg时阻塞的情况，有的话，大致是哪些原因？？？我做一个东西，偶尔会有
这种情况出现，一旦阻塞，再send就一直阻塞，除非重新加载模块，不知道是不是锁使用不当导致的。。。

  看了这文章，我一身冷汗，得赶紧查查我的代码去。

QUOTE:

获得自旋锁和释放自旋锁有好几个版本，因此让读者知道在什么样的情况下使用什么版本的获得和释放锁的宏是非常必要的。

如果被保护的共享资源只在进程上下文访问和软中断上下文访问，那么当在进程上下文访问共享资源时，可能被软中断打断，从而可能进入软中断上下文来对被保护的共享资源访问，因此对于这种情况，对共享资源的访问必须使用spin_lock_bh和spin_unlock_bh来保护。当然使用spin_lock_irq和spin_unlock_irq以及spin_lock_irqsave和spin_unlock_irqrestore也可以，它们失效了本地硬中断，失效硬中断隐式地也失效了软中断。但是使用spin_lock_bh和spin_unlock_bh是最恰当的，它比其他两个快。

如果被保护的共享资源只在进程上下文和tasklet或timer上下文访问，那么应该使用与上面情况相同的获得和释放锁的宏，因为tasklet和timer是用软中断实现的。

如果被保护的共享资源只在一个tasklet或timer上下文访问，那么不需要任何自旋锁保护，因为同一个tasklet或timer只能在一个CPU上运行，即使是在SMP环境下也是如此。实际上tasklet在调用tasklet_schedule标记其需要被调度时已经把该tasklet绑定到当前CPU，因此同一个tasklet决不可能同时在其他CPU上运行。timer也是在其被使用add_timer添加到timer队列中时已经被帮定到当前CPU，所以同一个timer绝不可能运行在其他CPU上。当然同一个tasklet有两个实例同时运行在同一个CPU就更不可能了。

如果被保护的共享资源只在两个或多个tasklet或timer上下文访问，那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护，不必使用_bh版本，因为当tasklet或timer运行时，不可能有其他tasklet或timer在当前CPU上运行。如果被保护的共享资源只在一个软中断（tasklet和timer除外）上下文访问，那么这个共享资源需要用spin_lock和spin_unlock来保护，因为同样的软中断可以同时在不同的CPU上运行。

如果被保护的共享资源在两个或多个软中断上下文访问，那么这个共享资源当然更需要用spin_lock和spin_unlock来保护，不同的软中断能够同时在不同的CPU上运行。

如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。而在中断处理句柄中使用什么版本，需依情况而定，如果只有一个中断处理句柄访问该共享资源，那么在中断处理句柄中仅需要spin_lock和spin_unlock来保护对共享资源的访问就可以了。因为在执行中断处理句柄期间，不可能被同一CPU上的软中断或进程打断。但是如果有不同的中断处理句柄访问该共享资源，那么需要在中断处理句柄中使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。

在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代，那具体应该使用哪一个也需要依情况而定，如果可以确信在对共享资源访问前中断是使能的，那么使用spin_lock_irq更好一些，因为它比spin_lock_irqsave要快一些，但是如果你不能确定是否中断使能，那么使用spin_lock_irqsave和spin_unlock_irqrestore更好，因为它将恢复访问共享资源前的中断标志而不是直接使能中断。当然，有些情况下需要在访问共享资源时必须中断失效，而访问完后必须中断使能，这样的情形使用spin_lock_irq和spin_unlock_irq最好。

需要特别提醒读者，spin_lock用于阻止在不同CPU上的执行单元对共享资源的同时访问以及不同进程上下文互相抢占导致的对共享资源的非同步访问，而中断失效和软中断失效却是为了阻止在同一CPU上软中断或中断对共享资源的非同步访问。

作者: duanjigang 发布时间: 2010-01-12

又找到两篇好文章啊

Linux 内核的同步机制，第 1 部分
http://www.ibm.com/developerworks/cn/linux/l-synch/part1/
Linux 内核的同步机制，第 2 部分
http://www.ibm.com/developerworks/cn/linux/l-synch/part2/

作者: duanjigang 发布时间: 2010-01-12

QUOTE:

原帖由 duanjigang 于 2010-1-12 15:31 发表
又找到两篇好文章啊

Linux 内核的同步机制，第 1 部分
http://www.ibm.com/developerworks/cn/linux/l-synch/part1/
Linux 内核的同步机制，第 2 部分
http://www.ibm.com/developerworks/cn/lin ...

看你们的讨论受益匪浅

http://www.ibm.com/developerworks/cn/linux/上的文章向来经典去拜读下

作者: ubuntuer 发布时间: 2010-01-12

在init_mem_list函数里的第一次分配的话，是不是应该要添加一行代码：
  if(!plist->list)
      {
         plist->list = p;
         plist->list->next = p;//添加代码。否则在第二次循环时候的p->next指针为空，与第一次分配的不能形成链表
         plist->ptr = p;
         continue;
      }

作者: libra811 发布时间: 2010-01-12

QUOTE:

原帖由 libra811 于 2010-1-12 16:30 发表
在init_mem_list函数里的第一次分配的话，是不是应该要添加一行代码：
  if(!plist->list)
      {
         plist->list = p;
         plist->list->next = p;//添加代码。否则在第二次循环时候 ...

p是循环中的一个临时变量，这个分配的原则是如果链表头空，就把当前新节点给链表头。
如果不空，就把新节点加入到链表头和后续节点之间。
您这句似乎没有必要，呵呵，也看不懂这样写的意图

作者: duanjigang 发布时间: 2010-01-12

说是“简单”，但还是不大明白……

作者: flydream81 发布时间: 2010-01-12

QUOTE:

原帖由 flydream81 于 2010-1-12 22:25 发表
说是“简单”，但还是不大明白……

呵呵，是目的不明白还是实现不明白？

目的是：
初始化时申请足够用的内存，然后运行时根据用户需求，调用申请接口时，就分配一个该类型的节点，也就是一个该类型的变量。
用户释放时，就把该节点放入内存池。为了省去频繁的malloc和free操作，提高内存分配和回收的效率。
实现方法：
首先从一个类型说起，一个类型的类存储就是一个双向链表，这个链表构成了一个栈，初始化时，初始化N个该类型的节点，挂在该链表下。链表每个节点下面挂一个节点，链表头在栈尾部，链表尾在栈顶部。
每次申请节点时，把链表尾的节点摘下来返回给用户，然后弹栈，也就是链表尾指针往前移动一个位置。
如果尾巴和头相等，则说明节点分配完了。
每次回收节点时，先把链表尾往移动一个位置，然后把回收的节点挂在链表尾上。

对于多个不同的类型，我们用了一个栈列表，或者说数组，数组每个元素就是一个类型的链表或者栈。

类型我们定义为0到255，用一个u_int8_t的变量标识。
进行申请时，根据类型值直接哈希到数组的对应链表上。
回收时，先根据节点地址，计算它的类型值，然后再哈希回去。---因为我们在分配内存时，刻意为每个节点多申请了一个字节，用这个字节存储类型值，这样回收就快了

不知道说清楚没有，呵呵

对了，我放上了图，应该比较清晰了

[ 本帖最后由 duanjigang 于 2010-1-13 10:55 编辑 ]

作者: duanjigang 发布时间: 2010-01-13

使用 spin_lock和spin_lock_bh的区别可以参考albcamus发表的精华文章
http://linux.chinaunix.net/bbs/viewthread.php?tid=656347&extra=page%3D3%26amp%3Bfilter%3Ddigest

我记得最后有个表的，很有用，可惜现在下不了附件，可以去网上搜搜

[ 本帖最后由 thomas_ar 于 2010-1-13 13:09 编辑 ]

作者: thomas_ar 发布时间: 2010-01-13

难道最近所有的附件都看不到？这是怎么一回事？？？