【笔记】Linux内核中的循环缓冲区

1. 有关ring buffer的理解

1)  ring buffer位首尾相接的buffer，即类似生活中的圆形跑道；

2)  空闲空间+数据空间=ring buffer大小

3)  ring buffer的读写，类似生活中在圆形跑道上的追赶游戏，领跑者位write，追赶着为read

4)  如果read跑的太快，追上write，追赶者read要停下来，否则游戏结束。即保证没有数据空间时，不再从ring buffer中读取数据；

5)  如果write跑的太快，反过来套圈要超过read，此时领跑者write也要停下来。即保证没有空闲空间时，不再往ring buffer中写入数据；

6) 所以，read和write之间的距离总是介于开区间(0, buffer大小)

2. linux2.6内核，kfifo的理解

假设buffer的大小为size，读指针为in，写指针为out

1) 在计算机中，整型数据加到最大值后溢出会回卷到0，从头开始）

2)buffer的长度必须是2的n次幂

3) buffer空闲空间和数据空间的大小

1> 空闲空间的大小=size-in+out

2> 空闲空间的大小=in-out

2.2 对数据空间大小计算的理解

本设计总能保证in前out前面的，in跑出unsigned int边界溢出后回卷。

因为buffer的大小是2的n次幂，而unsigned int也是2的n次幂（32位机器上，n=32），一般buffer大小不会超过unsigned int大小，即unsigned int被分成m个整块(m>=1)

第1种情况：

out+数据空间=in

空闲空间=size-数据控件=size-(in-out)=size-in+out

第2种情况：(in跑到unsigned int的边界后，溢出了)

out+数据空间=in，这个等式仍然成立。

所以：空闲空间=size-in+out，亦成立

2.3 写操作分析（读操作类似，不再赘述）

2.3.1 基本情况

设落在ring buffer内写指针为__in，读指针为__out，需要写入的空间大小为len, 其中

1. __in = fifo->in % (fifo->size - 1)  (读写指针都是从0开始算起)

2. __out = fifo->out % (fifo->size - 1)

3. __size = fifo->size

4.  len <= 空闲空间大小

2.3.2 写指针没有回卷

这种情况下，需要写两块buffer，做两次拷贝动作，设需要写入的大小为len，第一块空闲空间大小为left1，第二块为left2，需要第一次拷贝的大小为len1，第二次拷贝的大小为len2，len1 + len2 = len：

1. left1 = _size-__in;

2. len1 = min(len, left1) = min(len, _size-__in);

3. left2 = __out;

4. len2 = len - len1

2.3.3 写指针回卷

这种情况下，需要写一块buffer，做一次拷贝动作：

1. left1 = __out - __in <= __size - __in;

2. 而写入长度len <= 空闲空间大小，所以len <= left1 <= __size - __in，所以len1 = len, len1 = min(len, __size - __in)仍然成立

3. left2 = 0;

4. len2 = 0 = len -len1

2.3.4 两种特殊情况一般化

总结以上两种情形，第一块空闲空间大小为left1，第二块为left2，需要第一次拷贝的大小为len1，第二次拷贝的大小为len2，len1 + len2 = len，则通用情况如下：

1. len <= 空闲空间大小

2. len1 = min(len, _size-__in);

3. len2 = len -len1

附：linux2.6内核，kfifo的实现代码

unsigned int __kfifo_put(struct kfifo *fifo,
             unsigned char *buffer, unsigned int len)
{
    unsigned int l;

    len = min(len, fifo->size - fifo->in + fifo->out);

    /* 前提条件写入大小len不超过空闲空间大小 */

    smp_mb();

    /* 第一块写入空闲空间，大小为min(len, size-in) */
    l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
    memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

    /* 第二块写入空闲空间，大小为len-min(len, size-in) */
    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;

    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;

    return len;
}