Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <20200304031551.1326-1-cai@lca.pw> <20200304033329.GZ29971@bombadil.infradead.org>
 <20200304040515.GX2935@paulmck-ThinkPad-P72> <20200304043356.GC29971@bombadil.infradead.org>
 <20200304141021.GY2935@paulmck-ThinkPad-P72> <20200305151831.GM29971@bombadil.infradead.org>
 <20200305213946.GL2935@paulmck-ThinkPad-P72> <CANpmjNOtsdxh3YLcF-pUMua9afWfhg5P_2ziRGSMuT8Gi0c5TA@mail.gmail.com>
 <20200306165300.GC25710@bombadil.infradead.org> <20200306170316.GX2935@paulmck-ThinkPad-P72>
In-Reply-To: <20200306170316.GX2935@paulmck-ThinkPad-P72>
From:   Marco Elver <elver@google.com>
Date:   Fri, 6 Mar 2020 21:04:13 +0100
Message-ID: <CANpmjNOGCmTXLFR=ycdtTVtRSqbj75MzYOo5V8PZ47trpcVddg@mail.gmail.com>
Subject: Re: [PATCH -next] lib: disable KCSAN for XArray
To:     "Paul E. McKenney" <paulmck@kernel.org>
Cc:     Matthew Wilcox <willy@infradead.org>, Qian Cai <cai@lca.pw>,
        LKML <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Fri, 6 Mar 2020 at 18:03, Paul E. McKenney <paulmck@kernel.org> wrote:
>
> On Fri, Mar 06, 2020 at 08:53:00AM -0800, Matthew Wilcox wrote:
> > On Fri, Mar 06, 2020 at 02:38:39PM +0100, Marco Elver wrote:
> > > On Thu, 5 Mar 2020 at 22:39, Paul E. McKenney <paulmck@kernel.org> wrote:
> > > > On Thu, Mar 05, 2020 at 07:18:31AM -0800, Matthew Wilcox wrote:
> > > > > I have found three locations where we use the ->marks array:
> > > > >
> > > > > 1.
> > > > >                         unsigned long data = *addr & (~0UL << offset);
> > > > >                         if (data)
> > > > >                                 return __ffs(data);
> > > > >
> > > > > 2.
> > > > >         return find_next_bit(addr, XA_CHUNK_SIZE, offset);
> > > > > 3.
> > > > >         return test_bit(offset, node_marks(node, mark));
> > > > >
> > > > > The modifications -- all done with the spinlock held -- use the non-atomic
> > > > > bitops:
> > > > >         return __test_and_set_bit(offset, node_marks(node, mark));
> > > > >         return __test_and_clear_bit(offset, node_marks(node, mark));
> > > > >         bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
> > > > > (that last one doesn't really count -- it's done prior to placing the node
> > > > > in the tree)
> > > > >
> > > > > The first read seems straightforward; I can place a READ_ONCE around
> > > > > *addr.  The second & third reads are rather less straightforward.
> > > > > find_next_bit() and test_bit() are common code and use plain loads today.
> > > >
> > > > Yes, those last two are a bit annoying, aren't they?  I guess the first
> > > > thing would be placing READ_ONCE() inside them, and if that results in
> > > > regressions, have an alternative API for concurrent access?
> > >
> > > FWIW test_bit() is an "atomic" bitop (per atomic_bitops.txt), and
> > > KCSAN treats it as such. On x86 arch_test_bit() is not instrumented,
> > > and then in asm-generic/bitops/instrumented-non-atomic.h test_bit() is
> > > instrumented with instrument_atomic_read(). So on x86, things should
> > > already be fine for test_bit(). Not sure about other architectures.
> >
> > Hum.  It may well be documented as atomic, but is it?  Here's the
> > generic implementation:
> >
> > static inline int test_bit(int nr, const volatile unsigned long *addr)
> > {
> >         return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
> > }
> >
> > arch_test_bit is only used by the instrumented variants:
> >
> > $ git grep arch_test_bit include
> > include/asm-generic/bitops/instrumented-non-atomic.h:   return arch_test_bit(nr, addr);
> >
> > As far as I can tell, the generic version is what's used on x86.  Does
> > the 'volatile' qualifier save us here?

x86 uses its own implementation of test_bit(), which we had to address
early on, otherwise we would still have tons of false reports due to
test_bit() usage.

$ grep -E -A3 'test_bit|instrumented' arch/x86/include/asm/bitops.h
static __no_kcsan_or_inline bool constant_test_bit(long nr, const
volatile unsigned long *addr)
{
        /*
         * Because this is a plain access, we need to disable KCSAN here to
         * avoid double instrumentation via instrumented bitops.
         */
        return ((1UL << (nr & (BITS_PER_LONG-1))) &
                (addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
--
static __always_inline bool variable_test_bit(long nr, volatile const
unsigned long *addr)
--
#define arch_test_bit(nr, addr)                 \
        (__builtin_constant_p((nr))             \
         ? constant_test_bit((nr), (addr))      \
         : variable_test_bit((nr), (addr)))
--
#include <asm-generic/bitops/instrumented-atomic.h>
#include <asm-generic/bitops/instrumented-non-atomic.h>
#include <asm-generic/bitops/instrumented-lock.h>


For the asm-generic variant, the cast to volatile should have the same
effect as READ_ONCE today (except maybe on Alpha?).  We would still
need to use READ_ONCE() in asm-generic's test_bit() though, to avoid
KCSAN false positives on other architectures. The code-gen should be
the same. I can try to send a patch and see if that's ok to do.

> > find_next_bit() doesn't have the 'volatile' qualifier, so may still be
> > a problem?
>
> One approach would be to add the needed READ_ONCE().
>
> Another, if someone is crazy enough to do the work, would be to verify
> that the code output is as if there was a READ_ONCE().
>
> Thoughts?

find_next_bit() is difficult. The code is definitely not the same with
READ_ONCE(), there are 8 more instructions (x86-64). For now the only
thing we can do if we're fine with data-racy behaviour in
find_next_bit(), without changing it, is to use it with
'data_race(find_next_bit(...))'. Not great though. :-/

Thanks,
-- Marco