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;
Date:   Mon, 23 Sep 2019 20:32:15 +0800
From:   Boqun Feng <boqun.feng@gmail.com>
To:     Marco Elver <elver@google.com>
Cc:     Dmitry Vyukov <dvyukov@google.com>, Will Deacon <will@kernel.org>,
        kasan-dev <kasan-dev@googlegroups.com>,
        LKML <linux-kernel@vger.kernel.org>,
        Andrey Konovalov <andreyknvl@google.com>,
        Alexander Potapenko <glider@google.com>,
        "Paul E. McKenney" <paulmck@linux.ibm.com>,
        Paul Turner <pjt@google.com>, Daniel Axtens <dja@axtens.net>,
        Anatol Pomazau <anatol@google.com>,
        Andrea Parri <parri.andrea@gmail.com>,
        Alan Stern <stern@rowland.harvard.edu>,
        LKMM Maintainers -- Akira Yokosawa <akiyks@gmail.com>,
        Nicholas Piggin <npiggin@gmail.com>,
        Daniel Lustig <dlustig@nvidia.com>,
        Jade Alglave <j.alglave@ucl.ac.uk>,
        Luc Maranget <luc.maranget@inria.fr>
Subject: Re: Kernel Concurrency Sanitizer (KCSAN)
Message-ID: <20190923123215.GD11739@tardis>
References: <CANpmjNPJ_bHjfLZCAPV23AXFfiPiyXXqqu72n6TgWzb2Gnu1eA@mail.gmail.com>
 <20190920155420.rxiflqdrpzinncpy@willie-the-truck>
 <20190923043113.GA1080@tardis>
 <CACT4Y+a8qwBA_cHfZXFyO=E8qt2dFwy-ahy=cd66KcvFbpcyZQ@mail.gmail.com>
 <20190923085409.GB1080@tardis>
 <CACT4Y+YfkV80QF2qxjfHnBghM8Am8m_YHzCtPRfSmOrF-y3bbg@mail.gmail.com>
 <CANpmjNNX5gJ-CRZ-zg3vNzTcBh6+_zEFQzEGTVFKX-z_KwweVw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
        protocol="application/pgp-signature"; boundary="zx4FCpZtqtKETZ7O"
Content-Disposition: inline
In-Reply-To: <CANpmjNNX5gJ-CRZ-zg3vNzTcBh6+_zEFQzEGTVFKX-z_KwweVw@mail.gmail.com>
User-Agent: Mutt/1.12.1 (2019-06-15)
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk


--zx4FCpZtqtKETZ7O
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Mon, Sep 23, 2019 at 01:01:27PM +0200, Marco Elver wrote:
> On Mon, 23 Sep 2019 at 10:59, Dmitry Vyukov <dvyukov@google.com> wrote:
> >
> > On Mon, Sep 23, 2019 at 10:54 AM Boqun Feng <boqun.feng@gmail.com> wrot=
e:
> > >
> > > On Mon, Sep 23, 2019 at 10:21:38AM +0200, Dmitry Vyukov wrote:
> > > > On Mon, Sep 23, 2019 at 6:31 AM Boqun Feng <boqun.feng@gmail.com> w=
rote:
> > > > >
> > > > > On Fri, Sep 20, 2019 at 04:54:21PM +0100, Will Deacon wrote:
> > > > > > Hi Marco,
> > > > > >
> > > > > > On Fri, Sep 20, 2019 at 04:18:57PM +0200, Marco Elver wrote:
> > > > > > > We would like to share a new data-race detector for the Linux=
 kernel:
> > > > > > > Kernel Concurrency Sanitizer (KCSAN) --
> > > > > > > https://github.com/google/ktsan/wiki/KCSAN  (Details:
> > > > > > > https://github.com/google/ktsan/blob/kcsan/Documentation/dev-=
tools/kcsan.rst)
> > > > > > >
> > > > > > > To those of you who we mentioned at LPC that we're working on=
 a
> > > > > > > watchpoint-based KTSAN inspired by DataCollider [1], this is =
it (we
> > > > > > > renamed it to KCSAN to avoid confusion with KTSAN).
> > > > > > > [1] http://usenix.org/legacy/events/osdi10/tech/full_papers/E=
rickson.pdf
> > > > > >
> > > > > > Oh, spiffy!
> > > > > >
> > > > > > > In the coming weeks we're planning to:
> > > > > > > * Set up a syzkaller instance.
> > > > > > > * Share the dashboard so that you can see the races that are =
found.
> > > > > > > * Attempt to send fixes for some races upstream (if you find =
that the
> > > > > > > kcsan-with-fixes branch contains an important fix, please fee=
l free to
> > > > > > > point it out and we'll prioritize that).
> > > > > >
> > > > > > Curious: do you take into account things like alignment and/or =
access size
> > > > > > when looking at READ_ONCE/WRITE_ONCE? Perhaps you could initial=
ly prune
> > > > > > naturally aligned accesses for which __native_word() is true?
> > > > > >
> > > > > > > There are a few open questions:
> > > > > > > * The big one: most of the reported races are due to unmarked
> > > > > > > accesses; prioritization or pruning of races to focus initial=
 efforts
> > > > > > > to fix races might be required. Comments on how best to proce=
ed are
> > > > > > > welcome. We're aware that these are issues that have recently=
 received
> > > > > > > attention in the context of the LKMM
> > > > > > > (https://lwn.net/Articles/793253/).
> > > > > >
> > > > > > This one is tricky. What I think we need to avoid is an onslaug=
ht of
> > > > > > patches adding READ_ONCE/WRITE_ONCE without a concrete analysis=
 of the
> > > > > > code being modified. My worry is that Joe Developer is eager to=
 get their
> > > > > > first patch into the kernel, so runs this tool and starts spamm=
ing
> > > > > > maintainers with these things to the point that they start igno=
ring KCSAN
> > > > > > reports altogether because of the time they take up.
> > > > > >
> > > > > > I suppose one thing we could do is to require each new READ_ONC=
E/WRITE_ONCE
> > > > > > to have a comment describing the racy access, a bit like we do =
for memory
> > > > > > barriers. Another possibility would be to use atomic_t more wid=
ely if
> > > > > > there is genuine concurrency involved.
> > > > > >
> > > > >
> > > > > Instead of commenting READ_ONCE/WRITE_ONCE()s, how about adding
> > > > > anotations for data fields/variables that might be accessed witho=
ut
> > > > > holding a lock? Because if all accesses to a variable are protect=
ed by
> > > > > proper locks, we mostly don't need to worry about data races caus=
ed by
> > > > > not using READ_ONCE/WRITE_ONCE(). Bad things happen when we write=
 to a
> > > > > variable using locks but read it outside a lock critical section =
for
> > > > > better performance, for example, rcu_node::qsmask. I'm thinking s=
o maybe
> > > > > we can introduce a new annotation similar to __rcu, maybe call it
> > > > > __lockfree ;-) as follow:
> > > > >
> > > > >         struct rcu_node {
> > > > >                 ...
> > > > >                 unsigned long __lockfree qsmask;
> > > > >                 ...
> > > > >         }
> > > > >
> > > > > , and __lockfree indicates that by design the maintainer of this =
data
> > > > > structure or variable believe there will be accesses outside lock
> > > > > critical sections. Note that not all accesses to __lockfree field=
, need
> > > > > to be READ_ONCE/WRITE_ONCE(), if the developer manages to build a
> > > > > complex but working wake/wait state machine so that it could not =
be
> > > > > accessed in the same time, READ_ONCE()/WRITE_ONCE() is not needed.
> > > > >
> > > > > If we have such an annotation, I think it won't be hard for confi=
guring
> > > > > KCSAN to only examine accesses to variables with this annotation.=
 Also
> > > > > this annotation could help other checkers in the future.
> > > > >
> > > > > If KCSAN (at the least the upstream version) only check accesses =
with
> > > > > such an anotation, "spamming with KCSAN warnings/fixes" will be t=
he
> > > > > choice of each maintainer ;-)
> > > > >
> > > > > Thoughts?
> > > >
> > > > But doesn't this defeat the main goal of any race detector -- findi=
ng
> > > > concurrent accesses to complex data structures, e.g. forgotten
> > > > spinlock around rbtree manipulation? Since rbtree is not meant to
> > > > concurrent accesses, it won't have __lockfree annotation, and thus =
we
> > > > will ignore races on it...
> > >
> > > Maybe, but for forgotten locks detection, we already have lockdep and
> > > also sparse can help a little.
> >
> > They don't do this at all, or to the necessary degree.
> >
> > > Having a __lockfree annotation could be
> > > benefical for KCSAN to focus on checking the accesses whose race
> > > conditions could only be detected by KCSAN at this time. I think this
> > > could help KCSAN find problem more easily (and fast).
>=20
> Just to confirm, the annotation is supposed to mean "this variable
> should not be accessed concurrently". '__lockfree' may be confusing,
> as "lock-free" has a very specific meaning ("lock-free algorithm"),
> and I initially thought the annotation means the opposite. Maybe more
> intuitive would be '__nonatomic'.
>=20

Well, "__lockfree" means the variable will be accessed without holding a
lock, most likely in a lock-free algorithm. But I admit I haven't
thought too much about the name, so maybe it's a bad one ;-)

> My view, however, is that this will not scale. 1) Our goal is to
> *avoid* more annotations if possible. 2) Furthermore, any such

Understood. I don't have any objection to your goal, and I think
achieving that will really help developers.

> annotation assumes the developer already has understanding of all
> concurrently accessed variables; however, this may not be the case for
> the next person touching the code, resulting in an error. By

By introducing annotations as __lockfree/__nonatomic, won't it help pass
the understanding between developers? "the next person" should learn
about the design by reading the code (or document) rather than adding
some random code and see if KCSAN yells.

Just to be clear, my initial thought of introduing the annotation is to
have a better way to document the variable that cannot be accessed
"plainly" in a non mutual-exclusive environment, so that the fixes that
add READ_ONCE or WRITE_ONCE to accesses of those variables should be
considered useful.

> "whitelisting" variables, we would likely miss almost every serious
> bug.
>=20
> To enable/disable KCSAN for entire subsystems, it's already possible
> to use 'KCSAN_SANITIZE :=3Dn' in the Makefile, or 'KCSAN_SANITIZE_file.o
> :=3D n' for individual files.
>=20
> > > Out of curiosity, does KCSAN ever find a problem with forgotten locks
> > > involved? I didn't see any in the -with-fixes branch (that's
> > > understandable, given the seriousness, the fixes of this kind of
> > > problems could already be submitted to upstream once KCSAN found it.)
>=20
> The sheer volume of 'benign' data-races makes it difficult to filter
> through and get to these, but it certainly detects such issues.
>=20
> Thanks,
> -- Marco
>=20
> > This one comes to mind:
> > https://www.spinics.net/lists/linux-mm/msg92677.html
> >

Yeah, this one is a "forgotten lock" case in the wild.

> > Maybe some others here, but I don't remember which ones now:
> > https://github.com/google/ktsan/wiki/KTSAN-Found-Bugs

Thank you both for the information!

Regards,
Boqun

--zx4FCpZtqtKETZ7O
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQEzBAABCAAdFiEEj5IosQTPz8XU1wRHSXnow7UH+rgFAl2Iu0sACgkQSXnow7UH
+rgDqAf/blPQEppraEPp0L0MMMBL11v6v8tzlcck+j4FhNyajoaqiye/sG4uW+Mu
fIl25HkknEqzJvPnNVIalxBHL3yYm4UgOpAzRsPXaELrebvJRmTvq1OCzYDZkaP2
UTiv4FLEuLdjhw8pDaBfqgwjF6IzPrHo+CzSQrK0VJxJQcyhUYy3tZxVc5S4KCmc
ZXNV9zwguQtfSVMj+r5i0y45ybbgf0zmcP7h1x92/ucE04ea2K5v3giR2Y5VmnKa
vk+Lx9EOKFP+pM2f9oXh9j86Rjei+paMgS6Tm5Ds7pxcWbp85I40dmu76/vJv8Dw
M06gzd840Y7KtjInz7BKHsC3RWXPhw==
=/P5z
-----END PGP SIGNATURE-----

--zx4FCpZtqtKETZ7O--