linux kfifo 中 memory barrier的简要分析

  



1,kfifo introduction
    kfifo在linux kernel实现了一个fifo,具体可参考 kernel/kfifo.c 以及 include/
linux/kfifo.h,主要提供接口如下:

    __kfifo_put/__kfifo_get分别为写/读fifo的接口,没有使用lock的实现，仅允许一个
并发reader和并发writer的使用;
    kfifo_put/kfifo_get分别为写/读fifo的接口,使用lock的实现;

/**
 * __kfifo_put - puts some data into the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: the data to be added.
 * @len: the length of the data to be added.
 *
 * This function copies at most @len bytes from the @buffer into
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __kfifo_put(struct kfifo *fifo,
                         unsigned char *buffer, unsigned int len)

/**
 * __kfifo_get - gets some data from the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: where the data must be copied.
 * @len: the size of the destination buffer.
 *
 * This function copies at most @len bytes from the FIFO into the
 * @buffer and returns the number of copied bytes.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __kfifo_get(struct kfifo *fifo,
                         unsigned char *buffer, unsigned int len)


/**
 * kfifo_put - puts some data into the FIFO
 * @fifo: the fifo to be used.
 * @buffer: the data to be added.
 * @len: the length of the data to be added.
 *
 * This function copies at most @len bytes from the @buffer into
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.
 */
static inline unsigned int kfifo_put(struct kfifo *fifo,
                                     unsigned char *buffer, unsigned int len)

/**
 * kfifo_get - gets some data from the FIFO
 * @fifo: the fifo to be used.
 * @buffer: where the data must be copied.
 * @len: the size of the destination buffer.
 *
 * This function copies at most @len bytes from the FIFO into the
 * @buffer and returns the number of copied bytes.
 */
static inline unsigned int kfifo_get(struct kfifo *fifo,
                                     unsigned char *buffer, unsigned int len)





2,memory barrier使用简要分析

2.1 __kfifo_put()/__kfifo_get()实现[1]

为方便后续分析,给出两个函数的实现源码:

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

        /*
         * Ensure that we sample the fifo->out index -before- we
         * start putting bytes into the kfifo.
         */

        smp_mb();                                 /*===>B2*/

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

        /* then put the rest (if any) at the beginning of the buffer */
        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();                                 /*===>A1*/

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

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

        fifo->out += len;

        return len;
}



2.1 smp_rmb()/smp_wmb() pairing
1),smp_rmb():__kfifo_get() 和 smp_wmb():__kfifo_put()为一对smp memory barrier
pairing;

2),smp_wmb():__kfifo_put() 确保了 add the bytes to the kfifo -before- we update
the fifo->in index; smp_rmb():__kfifo_get() 确保 sample the fifo->in index
-before- we start removing bytes from the kfifo。  

smp_wmb()确保了对fifo->buffer 写操作 和 对fifo->in写操作的相对有序, 这个有序只是限定在
writer cpu(即执行__kfifo_put()的cpu)上, 如何使得writer cpu上对memory操作的顺序被reader
cpu(即执行__kfifo_get()的cpu)所感受到呢? 这个就需要smp_rmb()的配合使用.

smp_rmb()确保了对fifo->in读操作 和 对fifo->buffer 读操作的相对有序, 确保这两个内存操作的顺序
被reader CPU正确感受到.

3),kfifo context
从kfifo使用smp_wmb()/smp_rmb()的上下文来看, A2之前的fifo->in读操作 reader cpu一定可以得到
fifo->in内存中的准确值, 即:
    .如果writer cpu已经更新fifo->in(完成memory操作),那么reader cpu会看到fifo->in的最新
值以及fifo->buffer中的最新值；
    .如果writer cpu尚未完成更新fifo->in(完成memory操作),那么reader cpu会看到fifo->in之
前的内容，reader cpu可以正确读出当前fifo中内容；
    .即reader cpu一旦读出新的fifo->in,那么此时fifo->buffer一定包含和fifo->in对应的内容;如果
没有读出新的fifo->in,那么仍然可以正确读出之前的fifo->buffer内容;
2.2 smp_mb() pairing

1),smp_mb()可以确保之前的read/write memory operation和之后的read/write memory operation
相对有序发生,这个是smp_rmb()/smp_wmb()两者的任何组合所无法达到的效果.

smp_mb():__kfifo_get() 和 smp_mb():__kfifo_put() 为一对smp memory barrier pairing.

2),smp_mb():__kfifo_get()确保了 "we remove the bytes from the kfifo -before- we
update the fifo->out index"; 即确保 完成读出当前请求fifo->buffer的内容后，再fifo->out +=
len. ( read memory opearation before completing write memory operation )


3),smp_mb():__kfifo_put()确保了 " we sample the fifo->out index -before- we start
putting bytes into the kfifo"; 即确保 读出fifo->out 后，再向fifo->buffer写入当前请求的
内容( read memory opearation before completing write memory operation )

4),kfifo context

reader cpu 确保 读出fifo->buffer的数据后,才会更新fifo->out; writer cpu只有读出最新的fifo->out
后,才会向fifo->buffer写入数据.

3,reference
[1], linux kernel 2.6.27-rc2 sour