内容简介：1、前言最近项目中用到一个环形缓冲区（ring buffer），代码是由linux内核的kfifo改过来的。缓冲区在文件系统中经常用到，通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B，进程B需要对进程A传的数据进行处理并写入文件，如果B没有处理完，则A要延迟发送。为了保证进程A减少等待时间，可以在A和B之间采用一个缓冲区，A每次将数据存放在缓冲区中，B每次冲缓冲区中取。这是典型的生产者和消费者模型，缓冲区中数据满足FIFO特性，因此可以采用队列进行实现。Linux内
| 编辑推荐: |
| 本文来自于cnblogs，介绍了 linux 内核kfifo，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;
}
测试结果如下所示：
以上所述就是小编给大家介绍的《linux内核数据结构之kfifo》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- Linux 内核101：进程数据结构
- 从文件系统的数据结构看 Linux 内核设计
- 数据结构 – 用于构建文件系统的数据结构？
- 荐 用Python解决数据结构与算法问题（三）：线性数据结构之栈
- 内核必须懂(六): 使用kgdb调试内核
- 数据库索引背后的数据结构
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
JavaScript设计模式
Ross Harmes、Dustin Diaz / 谢廷晟 / 人民邮电出版社 / 2008 / 45.00元
本书共有两部分。第一部分给出了实现具体设计模式所需要的面向对象特性的基础知识，主要包括接口、封装和信息隐藏、继承、单体模式等内容。第二部分则专注于各种具体的设计模式及其在JavaScript语言中的应用，主要介绍了工厂模式、桥接模式、组合模式、门面模式等几种常见的模式。为了让每一章中的示例都尽可能地贴近实际应用，书中同时列举了一些JavaScript 程序员最常见的任务，然后运用设计模式使其解决方......一起来看看 《JavaScript设计模式》 这本书的介绍吧!
