读Linux内核kfifo
程序员文章站
2022-07-14 16:22:10
...
内核kfifo简约高效,匠心独运,有一下特点:
- 保证缓冲区大小为2的次幂,不是的向上取整为2的次幂。
- 使用无符号整数保存输入(in)和输出(out)的位置,在输入输出时不对in和out的值进行模运算,而让其自然溢出,并能够保证in-out的结果为缓冲区中已存放的数据长度。
- 将需要取模的运算用 & 操作代替( a % size = (a & (size − 1)) ), 这需要size保证为2的次幂。
- 使用内存屏障(Memory Barrier)技术,实现单消费者和单生产者对kfifo的无锁并发访问,多个消费者、生产者的并发访问还是需要加锁的(本文不涉及)。
以下为删改后可运行的代码:
// kfifo.h
#ifndef _LINUX_KFIFO_H
#define _LINUX_KFIFO_H
#include <stddef.h>
typedef int gfp_t;
struct __kfifo {
unsigned int in;
unsigned int out;
unsigned int mask;
unsigned int esize;
void *data;
};
extern int __kfifo_alloc(struct __kfifo *fifo, unsigned int size,
size_t esize);
extern void __kfifo_free(struct __kfifo *fifo);
extern int __kfifo_init(struct __kfifo *fifo, void *buffer,
unsigned int size, size_t esize);
extern unsigned int __kfifo_in(struct __kfifo *fifo,
const void *buf, unsigned int len);
extern unsigned int __kfifo_out(struct __kfifo *fifo,
void *buf, unsigned int len);
extern unsigned int __kfifo_out_peek(struct __kfifo *fifo,
void *buf, unsigned int len);
#endif
// kfifo.c
#include "ringbuffer.h"
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#define min(a, b) (((a) < (b)) ? (a) : (b))
static bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
/*
* internal helper to calculate the unused elements in a fifo
*/
static inline unsigned int kfifo_unused(struct __kfifo *fifo)
{
return (fifo->mask + 1) - (fifo->in - fifo->out);
}
int __kfifo_alloc(struct __kfifo* fifo, unsigned int size,
size_t esize)
{
/*
* round down to the next power of 2, since our 'let the indices
* wrap' technique works only in this case.
*/
// size = roundup_pow_of_two(size);
assert(is_power_of_2(size));
fifo->in = 0;
fifo->out = 0;
fifo->esize = esize;
if (size < 2) {
fifo->data = NULL;
fifo->mask = 0;
// return -EINVAL;
}
fifo->data = malloc(size * esize);
if (!fifo->data) {
fifo->mask = 0;
// return -ENOMEM;
}
fifo->mask = size - 1;
return 0;
}
void __kfifo_free(struct __kfifo *fifo)
{
free(fifo->data);
fifo->in = 0;
fifo->out = 0;
fifo->esize = 0;
fifo->data = NULL;
fifo->mask = 0;
}
int __kfifo_init(struct __kfifo *fifo, void *buffer,
unsigned int size, size_t esize)
{
size /= esize;
// size = roundup_pow_of_two(size);
assert(is_power_of_2(size));
fifo->in = 0;
fifo->out = 0;
fifo->esize = esize;
fifo->data = buffer;
if (size < 2) {
fifo->mask = 0;
// return -EINVAL;
}
fifo->mask = size - 1;
return 0;
}
static void kfifo_copy_in(struct __kfifo *fifo, const void *src,
unsigned int len, unsigned int off)
{
unsigned int size = fifo->mask + 1;
unsigned int esize = fifo->esize;
unsigned int l;
off &= fifo->mask;
if (esize != 1) {
off *= esize;
size *= esize;
len *= esize;
}
l = min(len, size - off);
memcpy(fifo->data + off, src, l);
memcpy(fifo->data, src + l, len - l);
}
unsigned int __kfifo_in(struct __kfifo *fifo,
const void *buf, unsigned int len)
{
unsigned int l;
l = kfifo_unused(fifo);
if (len > l)
len = l;
kfifo_copy_in(fifo, buf, len, fifo->in);
fifo->in += len;
return len;
}
static void kfifo_copy_out(struct __kfifo *fifo, void *dst,
unsigned int len, unsigned int off)
{
unsigned int size = fifo->mask + 1;
unsigned int esize = fifo->esize;
unsigned int l;
off &= fifo->mask;
if (esize != 1) {
off *= esize;
size *= esize;
len *= esize;
}
l = min(len, size - off);
memcpy(dst, fifo->data + off, l);
memcpy(dst + l, fifo->data, len - l);
}
unsigned int __kfifo_out_peek(struct __kfifo *fifo,
void *buf, unsigned int len)
{
unsigned int l;
l = fifo->in - fifo->out;
if (len > l)
len = l;
kfifo_copy_out(fifo, buf, len, fifo->out);
return len;
}
unsigned int __kfifo_out(struct __kfifo *fifo,
void *buf, unsigned int len)
{
len = __kfifo_out_peek(fifo, buf, len);
fifo->out += len;
return len;
}
计算缓冲区中甚于空闲长度
static inline unsigned int kfifo_unused(struct __kfifo *fifo)
{
return (fifo->mask + 1) - (fifo->in - fifo->out);
}
- 此处fifo->mask + 1 即为缓冲区长度,这个好理解。
-
fifo->in - fifo->out 为已经写入长度
- 当in > out 时很好理解。
- 还有一种情况,就是in写满缓冲区尾部,折回到开头并且unsigned int 溢出,out不溢出。此时 in < out , in - out 还为已经写入长度?
- 还有一种情况,就是in写满缓冲区尾部,折回到开头并且unsigned int 溢出,out不溢出。此时 in < out , in - out 还为已经写入长度?
答案是 in – out 为负数(又将溢出),in – out 的值还是为buffer中数据的长度。
证明代码: - 当in > out 时很好理解。
unsigned char a = 1;
unsigned char b = 254;
unsigned char c = a-b;
printf(" %u \n",c);
(以上图片来自https://www.linuxidc.com/Linux/2016-12/137938.htm)
c++ 简单实现
#include <stdio.h>
class RingBuffer
{
public:
RingBuffer(unsigned int size);
~RingBuffer();
unsigned int get(void *pbuf, unsigned int len);
unsigned int put(const void *pbuf, unsigned int len);
//for debug
void print()
{
for(int i=0; i<mask_+1; i++)
{
printf("%c \n",data_[i]);
}
}
private:
unsigned int in_;
unsigned int out_;
unsigned int mask_;
unsigned char *data_;
unsigned int used()
{ return in_ - out_;}
unsigned int unused()
{ return mask_ + 1 - used();}
};
#include "ringBuffer.h"
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
/*
* a % b = (a & (b − 1))
*/
namespace
{
inline bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
}
RingBuffer::RingBuffer(unsigned int size)
: in_(0),
out_(0),
mask_(size - 1),
data_(new unsigned char[size])
{
assert(is_power_of_2(size) && size >= 2);
}
RingBuffer::~RingBuffer()
{
delete[] data_;
}
unsigned int RingBuffer::get(void *pbuf, unsigned int len)
{
unsigned char *buf = static_cast<unsigned char *>(pbuf);
// 读取数据长度不能超过 已有数据长度
len = std::min(len, used());
__sync_synchronize();
//对 out_ 取模
unsigned int off = out_ & mask_;
//mask_ + 1 - off == out_到缓冲区尾部的距离
unsigned int l = std::min(len, mask_ + 1 - off);
//先取后面out_到缓冲区尾部的数据,长度为l
memcpy(buf, data_ + off, l);
//再取剩余在缓冲区头部的数据,长度为len-l,如果len-l为0,则不会拷贝
memcpy(buf + l, data_, len - l);
__sync_synchronize();
//直接加len,当unsinged int 溢出时自动归0
out_ += len;
return len;
}
unsigned int RingBuffer::put(const void *pbuf, unsigned int len)
{
unsigned char *buf = static_cast<unsigned char *>(const_cast<void *>(pbuf));
//写入数据长度不能超过 甚于空间
len = std::min(len, unused());
//TODO 缓冲区自动扩容
__sync_synchronize();
unsigned int off = in_ & mask_;
// mask_ + 1 - off = in_ 到缓冲区尾部的距离
unsigned int l = std::min(len, mask_ + 1 - off);
memcpy(data_ + off, buf, l);
memcpy(data_, buf + l, len - l);
__sync_synchronize();
in_ += len;
return len;
}