欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

读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 时很好理解。
      读Linux内核kfifo
      读Linux内核kfifo
      • 还有一种情况,就是in写满缓冲区尾部,折回到开头并且unsigned int 溢出,out不溢出。此时 in < out , in - out 还为已经写入长度?
        读Linux内核kfifo

    答案是 in – out 为负数(又将溢出),in – out 的值还是为buffer中数据的长度。
    证明代码:

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;
}