簡介

kfifo是linux內核中的一個模塊。
在單消費者，單生產者情況下，可以達到不加鎖也能保證線程安全的效果。

路徑

linux/lib/kfifo.c，鏈接直達：https://github.com/torvalds/linux/blob/master/lib/kfifo.c
linux/include/linux/kfifo.h，鏈接直達：https://github.com/torvalds/linux/blob/master/include/linux/kfifo.h

數據結構

struct __kfifo {
    unsigned int    in; //寫指針
    unsigned int    out;//讀指針
    unsigned int    mask; //size-1
    unsigned int    esize;//單個元素的大小
    void        *data; //保存數據
};

接口函數

//創建
kfifo_alloc(fifo, size, gfp_mask)
//初始化
kfifo_init(fifo, buffer, size)
//釋放
kfifo_free(fifo)
//寫數組
kfifo_put(fifo, val)
//讀數組
kfifo_get(fifo, val)
//讀數組但不移除
kfifo_peek(fifo, val)
//寫多個數據
kfifo_in(fifo, buf, n)
//讀多個數據
kfifo_out(fifo, buf, n)
//讀多個數據但不移除
kfifo_out_peek(fifo, buf, n)
//fifo大小
kfifo_size(fifo)
//fifo數據長度
kfifo_len(fifo) 
//fifo是否為空
kfifo_is_empty(fifo)

實現

無鎖隊列核心

在改變讀寫指針的時候，應該是原子操作。這要求僅通過讀寫指針的關係來判斷剩餘空間長度，而不是用一個變量來記錄已使用長度。（更詳細解釋，可以看這個博主的文章：https://airekans.github.io/c/2015/10/12/linux-kernel-data-str...）
限制長度在2的整次冪就能支撐這種方式，而不僅僅是比求模效率高。

計算剩餘空間

static inline unsigned int kfifo_unused(struct __kfifo *fifo)
{
    return (fifo->mask + 1) - (fifo->in - fifo->out);
}

未利用size為2的整次冪這特性。

寫數據

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);
    /*
     * make sure that the data in the fifo is up to date before
     * incrementing the fifo->in index counter
     */
    smp_wmb();
}

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

off傳進來的時候，是fifo->in。
off &= fifo->mask;
這個操作有效利用size為2的整次冪，因為這個操作，後續的fifo->in增加，是不用考慮長度判斷的。
fifo->in += 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);
    /*
     * make sure that the data is copied before
     * incrementing the fifo->out index counter
     */
    smp_wmb();
}

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

讀寫的指針的操作是一樣的，兩者記錄了內存的位置。僅僅在計算剩餘空間時候有交叉比較。