linux 内核中的kfifo在应用层上的实现_linux内核数据结构之kfifo

我就是我 2023-01-10 13:19 262阅读 0赞

# 1、前言 #

最近项目中用到一个环形缓冲区(ring buffer)，代码是由linux内核的kfifo改过来的。缓冲区在文件系统中经常用到，通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B，进程B需要对进程A传的数据进行处理并写入文件，如果B没有处理完，则A要延迟发送。为了保证进程A减少等待时间，可以在A和B之间采用一个缓冲区，A每次将数据存放在缓冲区中，B每次冲缓冲区中取。这是典型的生产者和消费者模型，缓冲区中数据满足FIFO特性，因此可以采用队列进行实现。Linux内核的kfifo正好是一个环形队列，可以用来当作环形缓冲区。生产者与消费者使用缓冲区如下图所示：

![57c814a441d5774d54f045eba88f58ce.png][]

环形缓冲区的详细介绍及实现方法可以参考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创建一个kfifostruct kfifo *kfifo_init(unsigned char *buffer, unsigned int size, gfp_t gfp_mask, spinlock_t *lock);//给定size分配buffer和kfifostruct 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，

![6777ae8c87933901109f18b5ce7764da.png][]

(2)put一个buffer后

![9bde50710e70047d4e12b7a9121851bb.png][]

(3)get一个buffer后

![e7ab2cf25115fc53a544a95ac70aa73e.png][]

(4)当此时put的buffer长度超出in到末尾长度时，则将剩下的移到头部去

![a76233002de14d10e0f28407e4e89d0f.png][]

# 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 #include #include #include #include #include //判断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."); 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

[57c814a441d5774d54f045eba88f58ce.png]: /images/20221119/e4aa5c8fbe8d433d8cbfe9305738fc78.png
[6777ae8c87933901109f18b5ce7764da.png]: /images/20221119/bd50996cdc0646799e0b3d70185177aa.png
[9bde50710e70047d4e12b7a9121851bb.png]: /images/20221119/2f54e808c9ff40be97ee8789286c3bdb.png
[e7ab2cf25115fc53a544a95ac70aa73e.png]: https://img-blog.csdnimg.cn/img_convert/e7ab2cf25115fc53a544a95ac70aa73e.png
[a76233002de14d10e0f28407e4e89d0f.png]: https://img-blog.csdnimg.cn/img_convert/a76233002de14d10e0f28407e4e89d0f.png