昨天临下班的时候想到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; } |
#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刚刚来电话又要搞个恶心的任务。所以心情大坏)。
先这样。
联系客服