Date: Tue, 28 May 2019 11:34:36 +0200 From: Alexander Lochmann <alexander.lochmann@tu-dortmund.de> To: freebsd-fs@freebsd.org Cc: Horst Schirmeier <horst.schirmeier@tu-dortmund.de> Subject: RFC: LockDoc - Detecting Locking Bugs in the FreeBSD Kernel Message-ID: <67482bf7-be1a-8f8d-ca80-2087bfc8cf99@tu-dortmund.de>
next in thread | raw e-mail | index | archive | help
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--R8bcOoHpld8vLVY30TDF0wrUdb6YxMbAJ
Content-Type: multipart/mixed; boundary="f0bfobHOpjofq6rsGsDkAd5w5OsOYqjj6";
protected-headers="v1"
From: Alexander Lochmann <alexander.lochmann@tu-dortmund.de>
To: freebsd-fs@freebsd.org
Cc: Horst Schirmeier <horst.schirmeier@tu-dortmund.de>
Message-ID: <67482bf7-be1a-8f8d-ca80-2087bfc8cf99@tu-dortmund.de>
Subject: RFC: LockDoc - Detecting Locking Bugs in the FreeBSD Kernel
--f0bfobHOpjofq6rsGsDkAd5w5OsOYqjj6
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable
Hi folks,
during the past months we've been developing LockDoc, a trace-based
approach of Lock Analysis in the FreeBSD kernel.
LockDoc uses execution traces of an instrumented FreeBSd kernel to
automatically deduce
locking rules for all members of arbitrary kernel data structures.
The traces are gathered running a manually selected fs-specific subset
of the Linux Test Project in a virtual machine.
We use the Linux Test Project, because we weren't able to find such
benchmark suite for FreeBSD and we initially applied our approach to Linu=
x.
These locking rules can be used to generate a comprehensive locking
documentation and to reveal potential bugs.
LockDoc generates rules for each tuple of (data structure, member, {r,w})=
=2E
It completely ignores any atomic_*() function.
Accesses during initialization and destruction of objects are also ignore=
d.
The output of LockDoc looks like this:
cdev_priv member: cdp_c.si_usecount [r] (5 lock combinations)
hypotheses: 24
34.8% (24 out of 69 mem accesses): EMBOTHER(vnode.v_lock[r]) ->
EMBOTHER(vnode.v_interlock[w]) -> devmtx:89(sleep mutex[w])
34.8% (24 out of 69 mem accesses): EMBOTHER(vnode.v_lock[r]) ->
devmtx:89(sleep mutex[w])
34.8% (24 out of 69 mem accesses): EMBOTHER(vnode.v_lock[r]) ->
EMBOTHER(vnode.v_interlock[w])
34.8% (24 out of 69 mem accesses): EMBOTHER(vnode.v_lock[r])
63.8% (44 out of 69 mem accesses): EMBOTHER(vnode.v_lock[w]) ->
EMBOTHER(vnode.v_interlock[w]) -> devmtx:89(sleep mutex[w])
63.8% (44 out of 69 mem accesses): EMBOTHER(vnode.v_lock[w]) ->
EMBOTHER(vnode.v_interlock[w])
65.2% (45 out of 69 mem accesses): EMBOTHER(vnode.v_lock[w]) ->
devmtx:89(sleep mutex[w])
65.2% (45 out of 69 mem accesses): EMBOTHER(vnode.v_lock[w])
98.6% (68 out of 69 mem accesses): EMBOTHER(vnode.v_interlock[w])
-> devmtx:89(sleep mutex[w])
98.6% (68 out of 69 mem accesses): EMBOTHER(vnode.v_interlock[w])
! 100% (69 out of 69 mem accesses): devmtx:89(sleep mutex[w])
100% (69 out of 69 mem accesses): (no locks held)
In this example LockDoc concludes that the lock
"devmtx:89(sleep mutex[w])" is necessary for reading
cdev_priv.cdp_c.si_usecount.
In this case, devmtx means a global lock of type sleep mutex.
To be more precise, the write lock (--> "[w]") of devmtx is needed.
Btw, EMBSAME stands for the lock embedded in the data type being accessed=
=2E
EMBOTHER respectively stands for a lock embedded in another object
that is currently not accessed.
Based on this methodology, we can determine code locations that do not
adhere to the deduced locking rules.
The reports on rule-violating code include the stack trace and the
actual locks held.
We've now created a series of bug reports for the following data types:
struct devfs_dirent, devfs_mount, mount, namecache, pipepair, and vnode
We present the counterexamples for each tuple of (data structure,
member, {r,w}).
Depending on the complexity of the callgraph, the counterexamples are
either embedded in the callgraph or the callgraph is shown below them.
In the latter case, zooming can be enabled via a button in the heading.
We kindly ask you to have a look at our findings and send us some
comments back:
https://ess.cs.tu-dortmund.de/lockdoc-bugs/freebsd/
If you are interested in the derived locking rules, have a look at:
https://ess.cs.tu-dortmund.de/lockdoc-bugs/freebsd/all-txns-members-locks=
-hypo-nostack-nosubclasses.txt
It might be possible that LockDoc considers a certain access as a bug
due to an incomplete blacklist of init and destroy functions.
Hence, we appreciate any feedback refining our blacklist.
Best regards,
Alex and Horst
--=20
Technische Universit=C3=A4t Dortmund
Alexander Lochmann PGP key: 0xBC3EF6FD
Otto-Hahn-Str. 16 phone: +49.231.7556141
D-44227 Dortmund fax: +49.231.7556116
http://ess.cs.tu-dortmund.de/Staff/al
--f0bfobHOpjofq6rsGsDkAd5w5OsOYqjj6--
--R8bcOoHpld8vLVY30TDF0wrUdb6YxMbAJ
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCgAdFiEElhZsUHzVP0dbkjCRWT7tBbw+9v0FAlztAKwACgkQWT7tBbw+
9v1weg/+NVynCPz85Liz4TZShjNqqn+7Va9Suy6sLxoEwVEL3N7lLoZdTPafqpsp
a/RZNtmGNvosW1XZsmQ3xp19JKmVog0xs8MnhlyTCsY8Qm/ZqSSCN3c0VVnq1JTP
e0eXmSu7FR795X9ZkkycuO9HzZWypPBErgKgwuErlizGEDPoeZJaLJIhS3/7FecV
tq/0wm/aybfMX7f1JJK/zYC2u9DQDDBTTnRkjzMVc2iCQAuMXmOMpNirjla41LcB
KtcazudMbPNPN/3NxE+l0HFmkSM8CQ4QuikfiAbhgHHFEznoYJP0xlw4kQl2Xyjp
Bi26xRjDrbBL22eNi/aOtmrFdqWnddKRaXVtDsG4+m9NTwCf8s23sL9ctflf3tpB
u8S0XUV6CxvUAqtFUXxbIUhOOY13k1knGHC7AkPS99gJoSyuPAQvQ2Fe+jOaXlYM
DKQnOrs++G7f7Lg8VRTJ5MFqIIYZoH8w6rHj8xwxFabWKe0moO67opAd+Z37MgVq
0Ak+iditQWVvpu0dd+spUu0TbpCDfdU5dtTuSXYbaEDrWGrui5d0shBA7DR70yek
sziC2yR6+sDiLcraCLNGCGIJpZRYC7LfOFjZlwKfcJAyOIr0iBSe4ROO1Ibl28sr
t/zRI/5/tsfmzu4x753vaP9qJpiar1NlF6NoWvzNGAJnBWNaZP8=
=xQf/
-----END PGP SIGNATURE-----
--R8bcOoHpld8vLVY30TDF0wrUdb6YxMbAJ--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?67482bf7-be1a-8f8d-ca80-2087bfc8cf99>