kfifo.email.md · k18700474961/OS kernel test_1

Hello Will, hello all,

I've done some work on KFIFO memory ordering with concerns of this mail
thread. Hope it useful though the words are tired longer:)

First, I'll show two litmus tests to give a proof of the potential issues.
Then analyze and figure out all the possible sufferers from the whole
kfifo.h/kfifo.c code. Finally give my proposals.

The work is based on kernel v5.4 yet KFIFO code being long stable, and with
assumption of lock-less - only one reader and one writer.

### 1. LKMM litmus test warned KFIFO might have memory reordering issue.

==========

In kfifo.h/kfifo.c, the most straightforward dequeue/enqueue API is
kfifo_put() and kfifo_get(). Their simplified snippets like:
```
#define kfifo_get(fifo, val) \
                __ret = !kfifo_is_empty(__tmp); \
                if (__ret) { \
                        *(&val) = __kfifo->data[__kfifo->out]; \
                        smp_wmb(); \
                        __kfifo->out++; \
                } \

#define kfifo_put(fifo, val) \
                __ret = !kfifo_is_full(__tmp); \
                if (__ret) { \
                        __kfifo->data)[__kfifo->in] = __val; \
                        smp_wmb(); \
                        __kfifo->in++; \
                } \
```
Note that, kfifo_get()'s code sequence is read data - store to memory
location(&var) - write index, not just read data - write index, and the 1st
store depends on the preceding load.

I tried two litmus tests.

Test 1

------

C kfifo_put+kfifo_get+read_stale.litmus
```
(* 
 * Result: Sometimes
 *
 * This mimic litmus test demonstrates that kfifo_get may get stale data,
 * because it misses a read barrier between 'load .in' and 'load .data'.
 *
 * To keep out compiler impact, here use READ_ONCE/WRITE_ONCE pairs.
 *
 * in:  __kfifo.in
 * out: __kfifo.out
 * d:   __kfifo.data[0]
 * b:   reader addressable variable
*)

{
        b = -1;
}

P0(int *in, int *out, int *d)                   // kfifo_put
{
        if (*in == READ_ONCE(*out)) {           // fifo is empty
                WRITE_ONCE(*d, 1);
                smp_wmb();
                WRITE_ONCE(*in, *in + 1);
        }
}

P1(int *in, int *out, int *d, int *b)           // kfifo_get
{
        int r;

if (READ_ONCE(*in) != *out) {           // fifo is full
                r = READ_ONCE(*d);
                WRITE_ONCE(*b, r);
                smp_wmb();
                WRITE_ONCE(*out, *out + 1);
        }
}

exists (b=0)

Test result

------

Test kfifo_put+kfifo_get+read_stale Allowed
States 3
b=-1;
b=0;
b=1;
Ok
Witnesses
Positive: 1 Negative: 2
Condition exists (b=0)
Observation kfifo_put+kfifo_get+read_stale Sometimes 1 2
Time kfifo_put+kfifo_get+read_stale 0.03
Hash=3bcede3a44bb3c0f05467646f9c1921a
```
Test 2: same as test 1 except initializer and exists
------
```
C kfifo_put+kfifo_get+read_future.litmus

(* 
 * Result: Never
 *
 * This mimic litmus test demonstrates that kfifo_get never gets future data
 * because smp_wmb() can prevent itself from reordering 'load data; dependent
 * store; store .out' sequence.
 * In fact, smp_wmb() is heavy, control dependency is enough.
 *
 * To keep out compiler impact, here use READ_ONCE/WRITE_ONCE pairs.
 *
 * in:  __kfifo.in
 * out: __kfifo.out
 * d:   __kfifo.data[0]
 * b:   reader addressable variable
*)

{
        in = 1;         (* ensure reader first *)
        b = -1;
}

P1(int *in, int *out, int *d, int *b)           // kfifo_get
{
        int r;

exists (b=1)

Test result
------

Test kfifo_put+kfifo_get+read_future Allowed
States 1
b=0;
No
Witnesses
Positive: 0 Negative: 2
Condition exists (b=1)
Observation kfifo_put+kfifo_get+read_future Never 0 2
Time kfifo_put+kfifo_get+read_future 0.01
Hash=53ecfe93b2120d00a0bfc4cbb9fb9327
```
As Yulei Zhang and Guangrong Xiao reported, test 1 shows that kfifo_get()
might miss a read barrier between read index and read data, which should
cooperate with kfifo_put()'s write barrier.

But test 2 also shows that kfifo_get() has no data loss issue, its barrier
is strong enough to prevent writer from overwriting unread data. Instead,
the test gives a useful hint: kfifo_get's smp_wmb() could be replaced with
an even more weaker barrier, actually the reader just need to ensure
-itself- 'reading data' happen before 'updating index', the writer doesn't
care about what the reader read.

### 2. All KFIFO functions(macros) having direct relation to memory ordering.

==========

Kfifo has 3 shared writable members: .in .out .data. Operating on these
variables concurrently might suffer from memory reordering issues. Below
lists all the function(macro) in kfifo.h/kfifo.c, which having direct
operations on these members.

The list was scratched from GNU cflow, intermediate functions without direct
operations were omitted. Indent represents caller-callee relationship. 
```
   reader                   load   r/w   store        writer
 call chain                 index  data  index      call chain
---------------------------------------------------------------------
__kfifo_out                               y     __kfifo_in
   __kfifo_out_peek           y                     kfifo_unused*
        kfifo_copy_out*             y               kfifo_copy_in*
            (memcpy)                                    (memcpy)
            (smp_wmb)                                   (smp_wmb)
__kfifo_out_r                 y           y     __kfifo_in_r
    __KFIFO_PEEK*                   y               __KFIFO_POKE*
    kfifo_copy_out*                 y               kfifo_copy_in*
        (memcpy)                                        (memcpy)
        (smp_wmb)                                       (smp_wmb)
__kfifo_to_user               y           y     __kfifo_from_user
    kfifo_copy_to_user*             y               kfifo_copy_from_user*
        (copy_to_user)                                  (copy_from_user)
        (smp_wmb)                                       (smp_wmb)
__kfifo_to_user_r             y           y     __kfifo_from_user_r
    __KFIFO_PEEK*                   y               __KFIFO_POKE*
    kfifo_copy_to_user*             y               kfifo_copy_from_user*
        (copy_to_user)                                  (copy_from_user)
        (smp_wmb)                                       (smp_wmb)
kfifo_get                           y     y     kfifo_put
    kfifo_is_empty            y                     kfifo_len
    (smp_wmb)                                       (smp_wmb)
                                                                      
__kfifo_dma_out_prepare       y                 __kfifo_dma_in_prepare
__kfifo_dma_out_prepare_r     y                 __kfifo_dma_in_prepare_r
kfifo_dma_out_finish                      y     kfifo_dma_in_finish
__kfifo_dma_out_finish_r                  y     __kfifo_dma_in_finish_r
    __KFIFO_PEEK*                   y               __KFIFO_POKE*

kfifo_peek                          y
    kfifo_is_empty            y
    (smp_wmb)
__kfifo_out_peek_r            y
    __KFIFO_PEEK*                   y
        kfifo_copy_out*             y
        (memcpy)
        (smp_wmb)
kfifo_skip                                y
__kfifo_skip_r                            y
    __KFIFO_PEEK*                   y
kfifo_reset_out                           y
kfifo_reset                               y
```
 * KFIFO internal helpers(total 7).
() These are not native KFIFO functions(macros), list here for reference.

The table shows altogether 34 functions(macros) divided into 3 groups:
    5 pairs of dequeue/enqueue and their 10 helpers
    4 pairs of DMA relevance
    6 special cases

DMA relevance is out of my reach, I bypass them in the followings.

From the table and KFIFO code, we can get:

#### 2.1 Seven dequeue functions(macros) miss read barriers.

Not surprisingly, the 5 pairs of dequeue/enqueue all have similar code
sequence like kfifo_get/kfifo_put: load index - r/w data - store index,
either done directly or through helpers. In particular, they all call
smp_wmb() before updating index. Like litmus test 1 said, the reader
functions(macros) might miss read barriers to cooperate with writers'
barriers.

__kfifo_out_peek_r and kfifo_peek are also dequeue function(macro) except
that they do not update index. When reading data, they all suffer the same
issue like kfifo_get().

#### 2.2 __kfifo_out_peek_r and kfifo_peek's smp_wmb() are meaningless.

As above said they do no update index. So no successive write behaviors need
to be enforced. The barriers here are just overhead.

__kfifo_out_peek_r's smp_wmb() is imposed by internal helper
kfifo_copy_out(). Another API __kfifo_out_peek(not in the table) also
suffers this problem.

Actually all dequeue/enqueue functions' smp_wmb() are now bound with these
like internal helpers, sitting with r/w data, not sitting with update index.
For dequeue's solo peek action, this is problematic.

#### 2.3 kfifo_reset and kfifo_reset_out memory orders are fragile.

Though the document has given usage note, but in coding these 2 special
macros should better draw a more clearer line before subsequent memory
operations. Enforcing strong barriers can avoid unintentional stale data
case. This nearly doesn't increase overhead for their occasional usage.

#### 2.4 __kfifo_to_user and __kfifo_to_user_r's smp_wmb() can be omitted in
control dependency.

As litmus test 2 said, the reader side's write barrier might be too
heavy(in-order-commit CPU arches even need none cpu barriers in this scene).
It is tempted to replace them with 'if-clause'. In my view, at least
__kfifo_to_user and __kfifo_to_user_r can facilitate this, because their
code blocks have explicit error condition check logic just before updating
index, like:
```
        ret = kfifo_copy_to_user(fifo, to, len, fifo->out, copied);
        if (unlikely(ret)) {
                len -= ret;
                err = -EFAULT;
        } else
                err = 0;
        fifo->out += len;
```
### 3. Proposals.

==========

#### 3.1 To guarantee 100% correctness,

- 7 reader side functions(macros) add read barriers. I prefer
      smp_load_acquire().
    - kfifo_reset and kfifo_reset_out add smp_mb().

#### 3.2 To optimize performance(patching are aggressive),

- Remove __kfifo_out_peek_r and kfifo_peek's smp_wmb().
    - Remove __kfifo_to_user and __kfifo_to_user_r's smp_wmb(), put index
      updating code into 'if-clause'.

#### 3.3 To counteract increased overhead(even more aggressive optimization),

Just as tools/memory-model/Documentation suggests, "It is usually better to
use smp_store_release() instead of smp_wmb() and to use smp_load_acquire()
instead of smp_rmb()." Release-store overhead is a little less than wmb-rmb
chains. This should touch the right side functions(macros) in the above
table.

If using release-store chains, most {READ, WRITE}_ONCE issues might also be
solved.

### TODO:

1. I tried to torture out the bug but failed to find appropriate machine.
The attachment is an userspace app for ARMv7. List here for reference. To
use it in other arch, just replace smp_wmb() arch code in the header file.

2. Performance test again with DMA and compiler are all out of my arm.

So many pities though:(

Regards,
laokz

附件1：摘自内核kfifo_arm.h(https://gitee.com/laokz/OS-kernel-test/blob/master/kfifo_arm.h)

附件2：kfifo_reorder_test.c(https://gitee.com/laokz/OS-kernel-test/blob/master/kfifo_reorder_test.c)

k18700474961/OS kernel test_1

简介

发行版

贡献者

近期动态

k18700474961/OS kernel test_1 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

k18700474961/OS kernel test_1