From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx2.suse.de ([195.135.220.15]:60088 "EHLO mx1.suse.de" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1731364AbeHIAz7 (ORCPT ); Wed, 8 Aug 2018 20:55:59 -0400 From: NeilBrown To: Frank Filz , "'J. Bruce Fields'" Date: Thu, 09 Aug 2018 08:34:02 +1000 Cc: 'Jeff Layton' , 'Alexander Viro' , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, 'Martin Wilck' Subject: RE: [PATCH 0/4] locks: avoid thundering-herd wake-ups In-Reply-To: <01b001d42f5c$ed082e20$c7188a60$@mindspring.com> References: <153369219467.12605.13472423449508444601.stgit@noble> <20180808195445.GD23873@fieldses.org> <20180808200912.GE23873@fieldses.org> <01b001d42f5c$ed082e20$c7188a60$@mindspring.com> Message-ID: <87eff8trmt.fsf@notabene.neil.brown.name> MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Sender: linux-fsdevel-owner@vger.kernel.org List-ID: --=-=-= Content-Type: text/plain Content-Transfer-Encoding: quoted-printable On Wed, Aug 08 2018, Frank Filz wrote: >> On Wed, Aug 08, 2018 at 03:54:45PM -0400, J. Bruce Fields wrote: >> > On Wed, Aug 08, 2018 at 11:51:07AM +1000, NeilBrown wrote: >> > > If you have a many-core machine, and have many threads all wanting >> > > to briefly lock a give file (udev is known to do this), you can get >> > > quite poor performance. >> > > >> > > When one thread releases a lock, it wakes up all other threads that >> > > are waiting (classic thundering-herd) - one will get the lock and >> > > the others go to sleep. >> > > When you have few cores, this is not very noticeable: by the time >> > > the 4th or 5th thread gets enough CPU time to try to claim the lock, >> > > the earlier threads have claimed it, done what was needed, and > released. >> > > With 50+ cores, the contention can easily be measured. >> > > >> > > This patchset creates a tree of pending lock request in which >> > > siblings don't conflict and each lock request does conflict with its > parent. >> > > When a lock is released, only requests which don't conflict with >> > > each other a woken. >> > >> > Are you sure you aren't depending on the (incorrect) assumption that >> > "X blocks Y" is a transitive relation? >> > >> > OK I should be able to answer that question myself, my patience for >> > code-reading is at a real low this afternoon.... >>=20 >> In other words, is there the possibility of a tree of, say, exclusive > locks with >> (offset, length) like: >>=20 >> (0, 2) waiting on (1, 2) waiting on (2, 2) waiting on (0, 4) >>=20 >> and when waking (0, 4) you could wake up (2, 2) but not (0, 2), leaving a > process >> waiting without there being an actual conflict. > > That implies that the order the locks were received in was: > > (0,4) > (2,2) > (1,2) > (0,2) > > But couldn't (0,2) have been made only dependent on (0,4)? Correct. (0,2) would be a child if (0,4), but a sibling of (2,2). > Of course then > (1,2) is dependent on BOTH (2,2) and (0,2). Does this tree logic handle t= hat > case? No, there is no support for double dependencies. It is still possible for a lock request to be woken up which, which still cannot be satisfied. When one block lock is unlocked, a pending request might then be queued against a different blocking lock. > > On the other hand, there might be a fairness reason to make (0,2) wait for > (1,2) even though it could have been granted concurrently with (2,2) since > this dependency tree also preserves some of the order of lock requests. The locking API doesn't promise fairness, and I don't think we should try too hard to achieve it. Certainly we shouldn't actively fight it (so no LIFO queuing) but if we try harder than that I suspect it would just be needless complexity. Thanks, NeilBrown > > Frank --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEG8Yp69OQ2HB7X0l6Oeye3VZigbkFAltrb9sACgkQOeye3VZi gbkhuhAAwEMxEQ7gJ1RYLno+0/RVGyxQx33KedyYRyGF7Z8JbUua+/lgEXp1U++2 AaF31BapQm6R/HseXXSBc6csEZU3Sg8hupkQnyg2vEU7FZ++r5t/w9NDwJLyDKiW ok3hAz18njcR/PclK3wyp2s1rJmN5gZAO4FiJ+CRSFbfC4fhVUkA8Q/A1GliWXoe VQuZDQHIIEW5lH93vpeddv5wVKkon9GQ7PcfZmlWvGZnD/JnruiD3NxCB7NsJUI/ /62rUayosykSP1BQA8ohnB9IaYyiOt0nsVKG6NWPxUBaetH12bqQE+AYHU362drF AEUmFvF7S6Qrik4NAPXg+xmBA2AO9xBrr9qLg9a29l/LGiUNBX2BsY14aijbE8be BDFI/BVTPRhBb1KZW+xf76W33uQBaf5BOvv87sfIpLx/+wwyooiNztfTA+CR53YM +s9JWyhlmNo06wqw5fsSrGnuY0kfqKkO5HcgwgyJNj8uWWxery/DN5LU9lzBU2kN TVarh5s/KDW85kWizRSrPil009qrlPO1zoklPp8wGYHpFNESOUEYUE4eqCKHBugv dMVNdrKkbxh67cOze2w5CEY6LZzEms9tdHqe987qRAkkIScpKYUoQKsLV+M36t0f Lw2YgUdXXNnfitYYSb4Grra5VQWgeEW6abygxWXvIJNq549YJpM= =L7GN -----END PGP SIGNATURE----- --=-=-=--