From owner-freebsd-fs@freebsd.org Tue May 28 09:45:07 2019 Return-Path: Delivered-To: freebsd-fs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 51C5615BC4E2 for ; Tue, 28 May 2019 09:45:07 +0000 (UTC) (envelope-from alexander.lochmann@tu-dortmund.de) Received: from unimail.uni-dortmund.de (mx1.hrz.uni-dortmund.de [129.217.128.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "unimail.tu-dortmund.de", Issuer "TU Dortmund CA - G01" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 938577082B for ; Tue, 28 May 2019 09:45:01 +0000 (UTC) (envelope-from alexander.lochmann@tu-dortmund.de) Received: from [129.217.43.37] (kalamos.cs.uni-dortmund.de [129.217.43.37]) (authenticated bits=0) by unimail.uni-dortmund.de (8.16.0.41/8.16.0.41) with ESMTPSA id x4S9YaHQ002278 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Tue, 28 May 2019 11:34:36 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tu-dortmund.de; s=unimail; t=1559036076; bh=m4TH30rguyOqa/zDzXTfSKglLvnVWUb4KXIoF/hWKCg=; h=To:Cc:From:Subject:Date; b=bww2jPBVUWDPZjQ7HNKslGP8H5GsJ6G7LVEGVFdqVXyw5TE585nc+/M97NbPJLPdu RMvxhCc/qhiOqvixyMDeSPx45IfwlldO5YztddeZ1FWGT7a/UiOPlHhoNAPGrPI9eF gnQcnLYJbGGPiOU3xBI8sDKUED7+dloTukL0WbKg= To: freebsd-fs@freebsd.org Cc: Horst Schirmeier From: Alexander Lochmann Subject: RFC: LockDoc - Detecting Locking Bugs in the FreeBSD Kernel Openpgp: preference=signencrypt Autocrypt: addr=alexander.lochmann@tu-dortmund.de; prefer-encrypt=mutual; keydata= mQINBFQIyUEBEADZ+x+Ssg/46SiU66zm2lPGYAdqYfmXVv+sf/23+/KSj0FQHZKywzWjsmgR vWZZVlGJolwcW3MJ/g6ctZeOpfYiZVpzbZwNgKU0ETGjUmqmlq5/o5KnENKOimZzaKSaNn9p IC+EIeWXvu7pQjW0w1bK/RVVNw0p1Iz82W4Z+vKtD8CS+YJLAcZ6YoZMvQEg84O9odlV2Ryp oVj9EzHH40TWEdtgd4pQkaOks01PEr19sJXUjnP0VxLfs91AZjRnmGJKnI4HcrOKwquoQEeL DtHCxK0VNeoXCWkz33uBxSL5cicQ7D09hxjWthMilUpDZT94x0K452q4nybQ1TSLTYC8mlW+ xKUvJmqfHZbITJ10dTgjNvOe0kLbpXeQ1789lNmnA9bkQAK5Cefo55WbXmr1Mo3PV7y0XCib OaiijPlZo/Isc03EOK3lHPK8NuY8G+ftvphO4RyXCUWXw/o01cDnPaIEcTWkUbXvMhf/6ltP 1QWEfkguzGVjTw7Xssm9YuokC+P+49JKRyZzyCJZ022OxMlsX6c1BNZ4+cWUNmn6xr1xRNse SglpMLL1m3K1KuLf1hdAor6PBzFLiLa33lUhsWtg1ACFhpfZZOQRVas2McXTYUUpmCzOYI5F +km5q6cZStr9m7O3Y3DDGotiaJDpLtATwZ4MIM4ADbg/xl6ZgwARAQABtDZBbGV4YW5kZXIg TG9jaG1hbm4gPGFsZXhhbmRlci5sb2NobWFubkB0dS1kb3J0bXVuZC5kZT6JAj4EEwECACgF AlQIyUECGyMFCQlmAYAGCwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJEFk+7QW8Pvb9I34Q AIEGy9Pt1nK8r+0baVF5KBXzoZuQIQ7ZfxJ0MFrCQSvRYEWevm2a0p5lBDOpb/VL8VtYMVO2 xZewerWoXyWMIeWmmCeSuVGdLDT/YV6BA54KzJkptmXxQaUVdiY+Fl0jxFODAXvSxI36MdzQ PFMwcSqxs5lZaxxyUWPidwanaQ5QNkShY2ljFD8gnKALiCxd/PqexLRlLinvqJ01EArxmPum PeA6nckWh4PGk1IGm7FiNZ5TYhCaq9lh5Hg5LsSJhJrOfgeT92hI7cLEwjKvRLrjH+NzbNFW tX4gWlwUHU5afP71AY9RfNXt/Ul8w+R5CX6W9xaiuS5MZZS5SZYeHU5QAfqaomSRkVb2uqwf Lahx76ONwOtsVbMLshaA9mxsgMUNDhOYxyKQOnYz2qThwZloEOgICaxIZG7WJug0HL4YGXG7 EJdFn2fEs6WUCeZ1DWGUGf92N+AFMBBJ/HP1fVlkAwuubOF7QdPTrsGwd8Tz0tkFzxd/W496 OvGO/OZZCw+pKnDODJyXtBs3jr6cu9evEasiaQEVL+nfhTGyNVW+dldn6uj7tJ3qLQbuk+o4 BLrUwjWXLdA4nMEGgtm8WabEyjoolP2BfjMTgEFQHhxaW0t4fIYLO5kM3lNphwXxmA4Lys+x RCPyLSitlqwrqDW19v56NTipcAqsczgpGZRGuQINBFQIyUEBEACcIW4RnxXteHv/Hl4/l926 sozOCL8iwT/OD9QvL3171Y1MDX8bt8LneMoh5RG4SegtdVaA4jLkdv8BTmRbY7qZrzJjYJX4 PUyvmuZbqpa+PF1c5uqUcuhwpXlQAupL1dCgO5p1xbdCxEOB9Lm+2hUFJy1LsvidwieJdFqR l09a/IypKtqywJxa6sSJp9ZPPCPMJnJxIVzGqAwHWO84LfIX5I6BRUbqAhxljJm40Bk79z+P HdytD0SaTuWIhsVYRFchKLxqbXokUhJaWupE1v4xFe2Sqty9vSCrJZMRZRTLvngRxbJVHIJJ sK685HNS3QJSrFtql+SGMkPHpX92+ZCmyTH6DAQ3Y0MtjJTcoYKu3fI8KT9BSsLuuXUToX7Y l4RbFB5s0rwZ2XMweKJdkwypC5fSZmLtEwgimMQ4VfBBUPJCvHhmvOHKX3Wls99D7xYWP7Lr iinmjbduiaO/A+bLjAdLqqGJpjQ7T3z+vqxzp3IaeJ3ObSnnnPppcKVAf6qZqu5Yfc31q/OY n19WyGIhwK3MuuVmjatxMmGgkSxzgTTP3jFQ008qymPcgrvgOR+MECCIpXjOMfenOhhsKnhu F7hxUS/6JtYKsEMEwJXVN509sNhJiEzSY9q+VYn9IArHSBMmpi5l6XvI1iwPD9HRNursPxKV lfi8lQsC7zxuTQARAQABiQIlBBgBAgAPBQJUCMlBAhsMBQkJZgGAAAoJEFk+7QW8Pvb9EkkP /2LyGWWOoTAGBhzvgKiYzarS3WQNZCuFHSfB/XXg4SRSX3NsxGVZWdLvVVgzWo1+tC1Qk6wO IVQSSw20wQXe8boZ8yiB8eM4ohfS0lySO9gOkQLYLijWg3JIYwTbqyK2X8LpbCs7eUTXM9NO 6pmVtoc3LBBIXQElX8ir0BZZ19OCSConTkyVHYK6IbEJ11PxjJG5ZS7anI4FQt0muzykZrhk bmf5IV3DtJ/KUfhQjnJa2B/KoT7F6vpTCoyPtaBUHQXEAb2NaZVwF06WXsqfX4yleym3Jlfx Rfa4+BOJ4Gf2EFd3wYCsIb33ulaXBLWa8w3A/FdQSW9NBM4iYlPxRg+5eXn+oajpyKqPLetH WRNMN4NSHVSpu+JRqRlTDO3HCn/peQ0OB/Iaf3HN3DLZdbjtZY40xl1iR9TMgD2fn2MlAFy3 dSKfjeCAQYP9can1MgebE729MI7QhtzuUYdHy+iJO/ENNlSgFo5DLwRqssEGqWag0xWPgcni UAERITTzHJeevSeZh5ThHyD173Pwn+tIhR4bK5RFy/gnzwqHckl8Hw7o06m51yI4dUVeatNT mAiNrmW3iQnvehjLZOYXOXx4ovsWdvQn01dUo3gCXdEWQ5yQLOQRGTCcrq1hzCEd//viy9oT spNrcZJf1pbo3EKkCwUPAltq51ramtYzOu4K Message-ID: <67482bf7-be1a-8f8d-ca80-2087bfc8cf99@tu-dortmund.de> Date: Tue, 28 May 2019 11:34:36 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="R8bcOoHpld8vLVY30TDF0wrUdb6YxMbAJ" X-Rspamd-Queue-Id: 938577082B X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org; dkim=pass header.d=tu-dortmund.de header.s=unimail header.b=bww2jPBV; spf=pass (mx1.freebsd.org: domain of alexander.lochmann@tu-dortmund.de designates 129.217.128.51 as permitted sender) smtp.mailfrom=alexander.lochmann@tu-dortmund.de X-Spamd-Result: default: False [-6.13 / 15.00]; RCVD_VIA_SMTP_AUTH(0.00)[]; TO_DN_SOME(0.00)[]; R_SPF_ALLOW(-0.20)[+ip4:129.217.128.0/24]; HAS_ATTACHMENT(0.00)[]; RCVD_DKIM_ARC_DNSWL_MED(-0.50)[]; DKIM_TRACE(0.00)[tu-dortmund.de:+]; RCPT_COUNT_TWO(0.00)[2]; RCVD_IN_DNSWL_MED(-0.20)[51.128.217.129.list.dnswl.org : 127.0.11.2]; SIGNED_PGP(-2.00)[]; MX_GOOD(-0.01)[esa3.itmc.tu-dortmund.de,esa4.itmc.tu-dortmund.de]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+,1:+,2:+]; IP_SCORE(-0.00)[asn: 680(-0.02), country: DE(-0.00)]; ASN(0.00)[asn:680, ipnet:129.217.0.0/16, country:DE]; MID_RHS_MATCH_FROM(0.00)[]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; R_DKIM_ALLOW(-0.20)[tu-dortmund.de:s=unimail]; FROM_HAS_DN(0.00)[]; DWL_DNSWL_MED(0.00)[tu-dortmund.de.dwl.dnswl.org : 127.0.11.2]; NEURAL_HAM_SHORT(-0.82)[-0.818,0]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; MIME_GOOD(-0.20)[multipart/signed,multipart/mixed,text/plain]; DMARC_NA(0.00)[tu-dortmund.de]; TO_MATCH_ENVRCPT_SOME(0.00)[]; RBL_COMPOSITE_RCVD_IN_DNSWL_MED_DWL_DNSWL_MED(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCVD_COUNT_TWO(0.00)[2] X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 28 May 2019 09:45:07 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --R8bcOoHpld8vLVY30TDF0wrUdb6YxMbAJ Content-Type: multipart/mixed; boundary="f0bfobHOpjofq6rsGsDkAd5w5OsOYqjj6"; protected-headers="v1" From: Alexander Lochmann To: freebsd-fs@freebsd.org Cc: Horst Schirmeier 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--