内核循环缓冲区数据结构在用户态的使用

　忘记了之前是有个什么事情一时想起好像需要用个cycler buffer，手头一时又没有，懒得自己实现。就向同学要了个。后来好像也没有用到，倒是一直记得好像老早以前看到ldd上提到双向链表的时候有提到个kfifo，只是一直没有用到这个，所以一直没看。倒是无聊的时候想起过printk是否用的就是这个数据结构。

　　昨天临下班的时候想到kfifo这个东东，今天就抽点时间看看。

　　刚开始是把双向链表拎出来编一下看看，结果让我大吃一惊。居然没有list.h，看来fc从4以后开始倒退倒是有点佐证了。好在机器上还有linux-libc-headers的包，解包覆盖一下应该就ok了吧。不要高兴，还是不行。打开list.h一看，居然里面只包含了另一个文件，只扔给我一个#error，超ft。没办法，只好上内核源码里去拷了，于是把include/*都copy到了/usr/include。再编，靠，居然还是不过。nnd，再看list.h，居然还有个宏定义才能使用里面的inline函数，要不就extern reference了，郁闷。只好在源文件中加了：

#ifdef CONFIG_DEBUG_LIST #undef CONFIG_DEBUG_LIST #endif

　　然后再包含上linux/autoconf.h，这才一切ok。汗......

　　有了上面的折腾，在开始搞kfifo之前就先看看kfifo.h和他的实现吧。结果一看kfifo.h和kfifo.c，头文件里面extern了好几个kfifo.c里面实现的东东不说，还用了spinlock，看来直接用是没有指望了，还是dirty hack到user space算了。于是只能把文件copy出来dirty hack了。吭哧吭哧搞了一气，搞了个可用的东东开列如下：
　　kfifo.c:

#include "kfifo.h" #include #include #include #include struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size) {     struct kfifo *fifo;     fifo = malloc(sizeof(struct kfifo));     if (!fifo)         return (void*)(-ENOMEM);     fifo->buffer = buffer;     fifo->size = size;     fifo->in = fifo->out = 0;     return fifo; } struct kfifo *kfifo_alloc(unsigned int size) {     unsigned char *buffer;     struct kfifo *ret;     if (size & (size - 1)) {         fprintf(stderr,"size > 0x80000000\n");         size = roundup_pow_of_two(size);     }     buffer = malloc(size);     if (!buffer)         return (void *)(-ENOMEM);     ret = kfifo_init(buffer, size);     if ((unsigned long)ret<=0)     {         free(buffer);     }     return ret; } void kfifo_free(struct kfifo *fifo) {     free(fifo->buffer);     free(fifo); } unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len) {     unsigned int l;     len = min(len, fifo->size - fifo->in + fifo->out);         l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));     memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);     memcpy(fifo->buffer, buffer + l, len - l);     fifo->in += len;     return len; } unsigned int __kfifo_get(struct kfifo *fifo,              unsigned char *buffer, unsigned int len) {     unsigned int l;     len = min(len, fifo->in - fifo->out);     l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));     memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);     fifo->out += len;     return len; }

　　kfifo.h:

#ifndef _LINUX_KFIFO_H #define _LINUX_KFIFO_H #define __u32 unsigned long #define __u64 unsigned long long #define min(x,y) ({ \         typeof(x) _x = (x);     \         typeof(y) _y = (y);     \         (void) (&_x == &_y);            \         _x < _y ? _x : _y; }) #define max(x,y) ({ \         typeof(x) _x = (x);     \         typeof(y) _y = (y);     \         (void) (&_x == &_y);            \         _x > _y ? _x : _y; }) static inline int fls(int x) {     int r;     __asm__("bsrl %1,%0\n\t"             "jnz 1f\n\t"             "movl $-1,%0\n"             "1:" : "=r" (r) : "rm" (x));     return r+1; } static inline int fls64(__u64 x) {     __u32 h = x >> 32;     if (h)         return fls(h) + 32;     return fls(x); } static inline unsigned fls_long(unsigned long l) {     if (sizeof(l) == 4)         return fls(l);     return fls64(l); } static inline unsigned long roundup_pow_of_two(unsigned long x) {     return 1UL << fls_long(x - 1); } struct kfifo {     unsigned char *buffer;    /* the buffer holding the data */     unsigned int size;    /* the size of the allocated buffer */     unsigned int in;    /* data is added at offset (in % size) */     unsigned int out;    /* data is extracted from off. (out % size) */ }; struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size); struct kfifo *kfifo_alloc(unsigned int size); void kfifo_free(struct kfifo *fifo); unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len); unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len); static inline void __kfifo_reset(struct kfifo *fifo) {     fifo->in = fifo->out = 0; } static inline void kfifo_reset(struct kfifo *fifo) {     __kfifo_reset(fifo); } static inline unsigned int kfifo_put(struct kfifo *fifo,                      unsigned char *buffer, unsigned int len) {     unsigned int ret;     ret = __kfifo_put(fifo, buffer, len);     return ret; } static inline unsigned int kfifo_get(struct kfifo *fifo,                      unsigned char *buffer, unsigned int len) {     unsigned int ret;     ret = __kfifo_get(fifo, buffer, len);     if (fifo->in == fifo->out)         fifo->in = fifo->out = 0;     return ret; } static inline unsigned int __kfifo_len(struct kfifo *fifo) {     return fifo->in - fifo->out; } static inline unsigned int kfifo_len(struct kfifo *fifo) {     unsigned int ret;     ret = __kfifo_len(fifo);     return ret; } #endif

  
　　用起来还是不错的，初步测试了一下效果还行，在去掉了spinlock的保护之后还揣测了一段时间是不是把spinlock改成sem用来sync，不过看到代码的实现又觉得这个spinlock不是对fifo的index进行保护的，也就是说这个实现是免锁的。在kernel中的代码也不过是在smp的情况下加了mb而已。

　　贴一下测试的代码如下：

#define FIFO_LENGTH 4096 struct ll_param {     struct kfifo * fifo;     int msg_len; }; static struct ll_param fifo; void thread_reader(void * param) {     int read_len=0;     unsigned int counter=0;     unsigned char buffer[FIFO_LENGTH]={0};     struct ll_param * p=(struct ll_param *)param;          for(;;)     {         bzero(buffer,FIFO_LENGTH);         read_len=kfifo_get(p->fifo,buffer,FIFO_LENGTH);         if(read_len!=0)         {             printf("Read len:%d,buffer is:%s\n",read_len,buffer);         }         else         {             counter++;         }         if(counter>20)         {             break;         }         usleep(50000);     } } void thread_writer(void * param) {     unsigned int write_len=0;     unsigned int counter=0;     unsigned char buffer[32]={0};     struct ll_param * p=(struct ll_param *)param;          for(counter=0;counter<1000;counter++)     {         bzero(buffer,32);         sprintf((char *)buffer,"This is %d message.\n",counter);         write_len=kfifo_put(p->fifo,buffer,strlen((char *)buffer));         usleep(100);     } } int main(void) {     pthread_t pidr;     pthread_t pidw;     fifo.msg_len=10;     fifo.fifo=kfifo_alloc(FIFO_LENGTH);     pthread_create(&pidw,NULL,(void *)thread_writer,&fifo);     pthread_create(&pidr,NULL,(void *)thread_reader,&fifo);     pthread_join(pidr,NULL);     pthread_join(pidw,NULL);     kfifo_free(fifo.fifo);     printf("\nGoodbye!\n");     return 0; }

　　要说明的是，初步测了一下，似乎reader中用来get的buffer大小对受writer和reader之间不一致的速率的影响较大。比如如果reader里面定义的buffer长度设置为小于fifo长度，在writer和reader个子usleep不同时间时表现会不同。以后再慢慢找吧（boss刚刚来电话又要搞个恶心的任务。所以心情大坏）。

　　先这样。