Linux内核结构体--kfifo 环状缓冲区
1、前言
最近项目中用到一个环形缓冲区(ring buffer),代码是由linux内核的kfifo改过来的。缓冲区在文件系统中经常用到,通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B,进程B需要对进程A传的数据进行处理并写入文件,如果B没有处理完,则A要延迟发送。为了保证进程A减少等待时间,可以在A和B之间采用一个缓冲区,A每次将数据存放在缓冲区中,B每次冲缓冲区中取。这是典型的生产者和消费者模型,缓冲区中数据满足FIFO特性,因此可以采用队列进行实现。Linux内核的kfifo正好是一个环形队列,可以用来当作环形缓冲区。生产者与消费者使用缓冲区如下图所示:
环形缓冲区的详细介绍及实现方法可以参考http://en.wikipedia.org/wiki/Circular_buffer,介绍的非常详细,列举了实现环形队列的几种方法。环形队列的不便之处在于如何判断队列是空还是满。维基百科上给三种实现方法。
2、linux 内核kfifo
kfifo设计的非常巧妙,代码很精简,对于入队和出对处理的出人意料。首先看一下kfifo的数据结构:
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) */ spinlock_t *lock; /* protects concurrent modifications */ };
kfifo提供的方法有:
//根据给定buffer创建一个kfifo struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock); //给定size分配buffer和kfifo struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock); //释放kfifo空间 void kfifo_free(struct kfifo *fifo) //向kfifo中添加数据 unsigned int kfifo_put(struct kfifo *fifo, const unsigned char *buffer, unsigned int len) //从kfifo中取数据 unsigned int kfifo_put(struct kfifo *fifo, const unsigned char *buffer, unsigned int len) //获取kfifo中有数据的buffer大小 unsigned int kfifo_len(struct kfifo *fifo)
定义自旋锁的目的为了防止多进程/线程并发使用kfifo。因为in和out在每次get和out时,发生改变。初始化和创建kfifo的源代码如下:
struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock) { struct kfifo *fifo; /* size must be a power of 2 */ BUG_ON(!is_power_of_2(size)); fifo = kmalloc(sizeof(struct kfifo), gfp_mask); if (!fifo) return ERR_PTR(-ENOMEM); fifo->buffer = buffer; fifo->size = size; fifo->in = fifo->out = 0; fifo->lock = lock; return fifo; } struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock) { unsigned char *buffer; struct kfifo *ret; if (!is_power_of_2(size)) { BUG_ON(size > 0x80000000); size = roundup_pow_of_two(size); } buffer = kmalloc(size, gfp_mask); if (!buffer) return ERR_PTR(-ENOMEM); ret = kfifo_init(buffer, size, gfp_mask, lock); if (IS_ERR(ret)) kfree(buffer); return ret; }
在kfifo_init和kfifo_calloc中,kfifo->size的值总是在调用者传进来的size参数的基础上向2的幂扩展,这是内核一贯的做法。这样的好处不言而喻--对kfifo->size取模运算可以转化为与运算,如:kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)
kfifo的巧妙之处在于in和out定义为无符号类型,在put和get时,in和out都是增加,当达到最大值时,产生溢出,使得从0开始,进行循环使用。put和get代码如下所示:
static inline unsigned int kfifo_put(struct kfifo *fifo, const unsigned char *buffer, unsigned int len) { unsigned long flags; unsigned int ret; spin_lock_irqsave(fifo->lock, flags); ret = __kfifo_put(fifo, buffer, len); spin_unlock_irqrestore(fifo->lock, flags); return ret; } static inline unsigned int kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len) { unsigned long flags; unsigned int ret; spin_lock_irqsave(fifo->lock, flags); ret = __kfifo_get(fifo, buffer, len); //当fifo->in == fifo->out时,buufer为空 if (fifo->in == fifo->out) fifo->in = fifo->out = 0; spin_unlock_irqrestore(fifo->lock, flags); return ret; } unsigned int __kfifo_put(struct kfifo *fifo, const unsigned char *buffer, unsigned int len) { unsigned int l; //buffer中空的长度 len = min(len, fifo->size - fifo->in + fifo->out); /* * Ensure that we sample the fifo->out index -before- we * start putting bytes into the kfifo. */ smp_mb(); /* first put the data starting from fifo->in to buffer end */ l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l); /* then put the rest (if any) at the beginning of the buffer */ memcpy(fifo->buffer, buffer + l, len - l); /* * Ensure that we add the bytes to the kfifo -before- * we update the fifo->in index. */ smp_wmb(); fifo->in += len; //每次累加,到达最大值后溢出,自动转为0 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); /* * Ensure that we sample the fifo->in index -before- we * start removing bytes from the kfifo. */ smp_rmb(); /* first get the data from fifo->out until the end of the buffer */ l = min(len, fifo->size - (fifo->out & (fifo->size - 1))); memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l); /* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, fifo->buffer, len - l); /* * Ensure that we remove the bytes from the kfifo -before- * we update the fifo->out index. */ smp_mb(); fifo->out += len; //每次累加,到达最大值后溢出,自动转为0 return len; }
put和get在调用__put和__get过程都进行加锁,防止并发。从代码中可以看出put和get都调用两次memcpy,这针对的是边界条件。例如下图:蓝色表示空闲,红色表示占用。
(1)空的kfifo,
(2)put一个buffer后
(3)get一个buffer后
(4)当此时put的buffer长度超出in到末尾长度时,则将剩下的移到头部去
3、测试程序
仿照kfifo编写一个ring_buffer,现有线程互斥量进行并发控制。设计的ring_buffer如下所示:
/**@brief 仿照linux kfifo写的ring buffer *@atuher Anker date:2013-12-18 * ring_buffer.h * */ #ifndef KFIFO_HEADER_H #define KFIFO_HEADER_H #include <inttypes.h> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <errno.h> #include <assert.h> //判断x是否是2的次方 #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0)) //取a和b中最小值 #define min(a, b) (((a) < (b)) ? (a) : (b)) struct ring_buffer { void *buffer; //缓冲区 uint32_t size; //大小 uint32_t in; //入口位置 uint32_t out; //出口位置 pthread_mutex_t *f_lock; //互斥锁 }; //初始化缓冲区 struct ring_buffer* ring_buffer_init(void *buffer, uint32_t size, pthread_mutex_t *f_lock) { assert(buffer); struct ring_buffer *ring_buf = NULL; if (!is_power_of_2(size)) { fprintf(stderr,"size must be power of 2.\n"); return ring_buf; } ring_buf = (struct ring_buffer *)malloc(sizeof(struct ring_buffer)); if (!ring_buf) { fprintf(stderr,"Failed to malloc memory,errno:%u,reason:%s", errno, strerror(errno)); return ring_buf; } memset(ring_buf, 0, sizeof(struct ring_buffer)); ring_buf->buffer = buffer; ring_buf->size = size; ring_buf->in = 0; ring_buf->out = 0; ring_buf->f_lock = f_lock; return ring_buf; } //释放缓冲区 void ring_buffer_free(struct ring_buffer *ring_buf) { if (ring_buf) { if (ring_buf->buffer) { free(ring_buf->buffer); ring_buf->buffer = NULL; } free(ring_buf); ring_buf = NULL; } } //缓冲区的长度 uint32_t __ring_buffer_len(const struct ring_buffer *ring_buf) { return (ring_buf->in - ring_buf->out); } //从缓冲区中取数据 uint32_t __ring_buffer_get(struct ring_buffer *ring_buf, void * buffer, uint32_t size) { assert(ring_buf || buffer); uint32_t len = 0; size = min(size, ring_buf->in - ring_buf->out); /* first get the data from fifo->out until the end of the buffer */ len = min(size, ring_buf->size - (ring_buf->out & (ring_buf->size - 1))); memcpy(buffer, ring_buf->buffer + (ring_buf->out & (ring_buf->size - 1)), len); /* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + len, ring_buf->buffer, size - len); ring_buf->out += size; return size; } //向缓冲区中存放数据 uint32_t __ring_buffer_put(struct ring_buffer *ring_buf, void *buffer, uint32_t size) { assert(ring_buf || buffer); uint32_t len = 0; size = min(size, ring_buf->size - ring_buf->in + ring_buf->out); /* first put the data starting from fifo->in to buffer end */ len = min(size, ring_buf->size - (ring_buf->in & (ring_buf->size - 1))); memcpy(ring_buf->buffer + (ring_buf->in & (ring_buf->size - 1)), buffer, len); /* then put the rest (if any) at the beginning of the buffer */ memcpy(ring_buf->buffer, buffer + len, size - len); ring_buf->in += size; return size; } uint32_t ring_buffer_len(const struct ring_buffer *ring_buf) { uint32_t len = 0; pthread_mutex_lock(ring_buf->f_lock); len = __ring_buffer_len(ring_buf); pthread_mutex_unlock(ring_buf->f_lock); return len; } uint32_t ring_buffer_get(struct ring_buffer *ring_buf, void *buffer, uint32_t size) { uint32_t ret; pthread_mutex_lock(ring_buf->f_lock); ret = __ring_buffer_get(ring_buf, buffer, size); //buffer中没有数据 if (ring_buf->in == ring_buf->out) ring_buf->in = ring_buf->out = 0; pthread_mutex_unlock(ring_buf->f_lock); return ret; } uint32_t ring_buffer_put(struct ring_buffer *ring_buf, void *buffer, uint32_t size) { uint32_t ret; pthread_mutex_lock(ring_buf->f_lock); ret = __ring_buffer_put(ring_buf, buffer, size); pthread_mutex_unlock(ring_buf->f_lock); return ret; } #endif采用多线程模拟生产者和消费者编写测试程序,如下所示:
/**@brief ring buffer测试程序,创建两个线程,一个生产者,一个消费者。 * 生产者每隔1秒向buffer中投入数据,消费者每隔2秒去取数据。 *@atuher Anker date:2013-12-18 * */ #include "ring_buffer.h" #include <pthread.h> #include <time.h> #define BUFFER_SIZE 1024 * 1024 typedef struct student_info { uint64_t stu_id; uint32_t age; uint32_t score; }student_info; void print_student_info(const student_info *stu_info) { assert(stu_info); printf("id:%lu\t",stu_info->stu_id); printf("age:%u\t",stu_info->age); printf("score:%u\n",stu_info->score); } student_info * get_student_info(time_t timer) { student_info *stu_info = (student_info *)malloc(sizeof(student_info)); if (!stu_info) { fprintf(stderr, "Failed to malloc memory.\n"); return NULL; } srand(timer); stu_info->stu_id = 10000 + rand() % 9999; stu_info->age = rand() % 30; stu_info->score = rand() % 101; print_student_info(stu_info); return stu_info; } void * consumer_proc(void *arg) { struct ring_buffer *ring_buf = (struct ring_buffer *)arg; student_info stu_info; while(1) { sleep(2); printf("------------------------------------------\n"); printf("get a student info from ring buffer.\n"); ring_buffer_get(ring_buf, (void *)&stu_info, sizeof(student_info)); printf("ring buffer length: %u\n", ring_buffer_len(ring_buf)); print_student_info(&stu_info); printf("------------------------------------------\n"); } return (void *)ring_buf; } void * producer_proc(void *arg) { time_t cur_time; struct ring_buffer *ring_buf = (struct ring_buffer *)arg; while(1) { time(&cur_time); srand(cur_time); int seed = rand() % 11111; printf("******************************************\n"); student_info *stu_info = get_student_info(cur_time + seed); printf("put a student info to ring buffer.\n"); ring_buffer_put(ring_buf, (void *)stu_info, sizeof(student_info)); printf("ring buffer length: %u\n", ring_buffer_len(ring_buf)); printf("******************************************\n"); sleep(1); } return (void *)ring_buf; } int consumer_thread(void *arg) { int err; pthread_t tid; err = pthread_create(&tid, NULL, consumer_proc, arg); if (err != 0) { fprintf(stderr, "Failed to create consumer thread.errno:%u, reason:%s\n", errno, strerror(errno)); return -1; } return tid; } int producer_thread(void *arg) { int err; pthread_t tid; err = pthread_create(&tid, NULL, producer_proc, arg); if (err != 0) { fprintf(stderr, "Failed to create consumer thread.errno:%u, reason:%s\n", errno, strerror(errno)); return -1; } return tid; } int main() { void * buffer = NULL; uint32_t size = 0; struct ring_buffer *ring_buf = NULL; pthread_t consume_pid, produce_pid; pthread_mutex_t *f_lock = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t)); if (pthread_mutex_init(f_lock, NULL) != 0) { fprintf(stderr, "Failed init mutex,errno:%u,reason:%s\n", errno, strerror(errno)); return -1; } buffer = (void *)malloc(BUFFER_SIZE); if (!buffer) { fprintf(stderr, "Failed to malloc memory.\n"); return -1; } size = BUFFER_SIZE; ring_buf = ring_buffer_init(buffer, size, f_lock); if (!ring_buf) { fprintf(stderr, "Failed to init ring buffer.\n"); return -1; } #if 0 student_info *stu_info = get_student_info(638946124); ring_buffer_put(ring_buf, (void *)stu_info, sizeof(student_info)); stu_info = get_student_info(976686464); ring_buffer_put(ring_buf, (void *)stu_info, sizeof(student_info)); ring_buffer_get(ring_buf, (void *)stu_info, sizeof(student_info)); print_student_info(stu_info); #endif printf("multi thread test.......\n"); produce_pid = producer_thread((void*)ring_buf); consume_pid = consumer_thread((void*)ring_buf); pthread_join(produce_pid, NULL); pthread_join(consume_pid, NULL); ring_buffer_free(ring_buf); free(f_lock); return 0; }
总结:
len = min(len, fifo->size - fifo->in + fifo->out);
在 len 和 (fifo->size - fifo->in + fifo->out) 之间取一个较小的值赋给len。注意,当 (fifo->in == fifo->out+fifo->size) 时,表示缓冲区已满,此时得到的较小值一定是0,后面实际写入的字节数也全为0。
另一种边界情况是当 len 很大时(因为len是无符号的,负数对它来说也是一个很大的正数),这一句也能保证len取到一个较小的值,因为 fifo->in 总是大于等于 fifo->out ,所以后面的那个表达式
l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); 的值不会超过fifo->size的大小。
smp_mb(); smp_wmb(); 是加内存屏障,这里不是我们讨论的范围,你可以忽略它。
l = min(len, fifo->size - (fifo->in & (fifo->size - 1))); 是把上一步决定的要写入的字节数len “切开”,这里又使用了一个技巧。注意:实际分配给
fifo->buffer 的字节数 fifo->size,必须是2的幂,否则这里就会出错。既然 fifo->size 是2的幂,那么 (fifo->size-1) 也就是一个后面几位全为1的数,也就能保证(fifo->in & (fifo->size - 1)) 总为不超过 (fifo->size - 1)
的那一部分,和 (fifo->in)% (fifo->size - 1) 的效果一样。
这样后面的代码就不难理解了,它先向 fifo->in 到缓冲区末端这一块写数据,如果还没写完,在从缓冲区头开始写入剩下的,从而实现了循环缓冲。最后,把写指针后移 len 个字节,并返回len。
从上面可以看出,fifo->in的值可以从0变化到超过fifo->size的数值,fifo->out也如此,但它们的差不会超过fifo->size。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。