linux - 内核kfifo.c中in和out的问题【已解决】

Question

先上内核循环缓冲结构体的定义：

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

如果对“Linux内核中的循环缓冲区”不是很了解的话，可以先参考 这里。内核中有关kfifo.c和kfifo.h两个文件的源码以及该问题的具体情况，可以查看这里。

对于结构体内的in和out两个变量，内核是作如下处理的:1、在读入数据时增加in；2、在取出数据时增加out；3、当检测到两个相等的时候将它们复位归0。1和2不作讨论和分析，针对第3点的处理，内核代码如下：

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

        /*
         * optimization: if the FIFO is empty, set the indices to 0
         * so we don't wrap the next time
         */
        if (fifo->in == fifo->out)
                fifo->in = fifo->out = 0;

        spin_unlock_irqrestore(fifo->lock, flags);

        return ret;
}

问题：当数据写入速度大于读取速度的时候，in和out的值将永远不会相等，也就是说buffer永远是有数据的，这样的话in和out都存在超出自身数值表示范围，从而导致错误？

针对这个问题，不知大家有什么好的建议？

Answer 1

I misread your question before.

From the perspective of source code implementation, it is indeed possible for in and out to overflow, but the situation is very extreme: every time the data is read, there is less data than the current buffer, and this situation Continue until the data written exceeds 4GB. Usually this should not be encountered; given the possible consequences of Murphy's Law, it does still need to be considered.

But think about it again, will overflow really cause a program error?

Go back and take a closer look at the code inside __kfifo_put(). It is implemented like this when writing:

    /* 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);

Note (fifo->in & (fifo->size - 1) The & symbol is used here instead of % fifo->size directly. In other words, size must be set to 2 during initialization. nth power (this limit is reasonable in the kernel, because the space allocated by the kernel is usually a multiple of 2, such as a page).

On processors like x86 where overflow is equivalent to a modulo operation, there is actually "just" no risk for the current write operation. Similarly, since in/out are both unsigned int, in the subsequent kfifo_get/kfifo_len, in - out (for example, 2 - 4294967295, you can try), the result is still "exactly" correct.

The conclusion is that it is really risk-free (provided that the overflow and unsigned integer subtraction operations are similar to those of x86 processors).

I have to say that the developers of the kernel source code are so stingy that they are not willing to write one more assignment operation.

---

Since you have turned to the source code, why not take a closer look at the implementation of ? kfifo_put()

The code it calls is enough to explain your problem: __kfifo_put() Before writing, it will compare the length of the data to be written and the maximum writable length of the buffer, whichever is smaller. or, writes, and then returns the written data length. There are only a few lines of specific code, so go check it out yourself. __kfifo_put()