On Fri, Jun 6, 2014 at 10:57 PM, Kostya Serebryany <kcc at google.com> wrote:> As for the deadlocks, indeed it is possible to add deadlock detection > directly to std::mutex and std::spinlock code. > It may even end up being more efficient than a standalone deadlock > detector -- > but only if we can add an extra word to the mutex/spinlock object. > The deadlock detector's overhead comes primarily from two tasks: > 1. get the metadata for the lock in question. > 2. query the lock-acquisition-order graph to see if there is a loop. > > If the lock-acquisition-order graph is sparse (99% of cases we've seen), > then the task #1 may constitute up to 50% of the overhead. > If we can add a word to std::mutex/std::spinlock data structures then the > task #1 becomes trivial. >I don't see any reason not to reserve a word in the mutex so that in (an ABI-compatible) debug build the mutex can support deadlock detection. Some people are super concerned about having an extra word in a mutex, but I'm not at all. For libc++, it would probably need to be behind an ABI-breaking macro on Mac and FreeBSD, but we haven't committed to any ABI stability on Linux, so we could probably enable it by default there, and get into build bots. Maybe bring this up on the cfe-dev list to discuss with Marshall and other folks interested in libc++? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140606/fa94e597/attachment.html>
On 7 Jun 2014, at 07:50, Chandler Carruth <chandlerc at google.com> wrote:> I don't see any reason not to reserve a word in the mutex so that in (an ABI-compatible) debug build the mutex can support deadlock detection. Some people are super concerned about having an extra word in a mutex, but I'm not at all.Making a mutex span multiple cache lines can have very serious and unpredictable performance impacts in the contended case (if you're not contended, a mutex is probably the wrong synchronisation primitive for you) on modern CPUs.> For libc++, it would probably need to be behind an ABI-breaking macro on Mac and FreeBSD, but we haven't committed to any ABI stability on Linux, so we could probably enable it by default there, and get into build bots. > > Maybe bring this up on the cfe-dev list to discuss with Marshall and other folks interested in libc++?On FreeBSD and OS X, the underlying pthread_mutex can already do deadlock detection, so I don't see why you'd need to add another word. The PTHREAD_MUTEX_ERRORCHECK attribute has been part of POSIX since 1997, so I'd expect it to be supported everywhere. For FreeBSD, we also had a GSoC student a couple of years ago who ported the WITNESS lock order reversal checking framework from the kernel to userspace, for more detailed checking. David
On Sat, Jun 7, 2014 at 10:16 AM, David Chisnall <David.Chisnall at cl.cam.ac.uk> wrote:> On 7 Jun 2014, at 07:50, Chandler Carruth <chandlerc at google.com> wrote: > >> I don't see any reason not to reserve a word in the mutex so that in (an ABI-compatible) debug build the mutex can support deadlock detection. Some people are super concerned about having an extra word in a mutex, but I'm not at all. > > Making a mutex span multiple cache lines can have very serious and unpredictable performance impacts in the contended case (if you're not contended, a mutex is probably the wrong synchronisation primitive for you) on modern CPUs.Are we currently bumping up against cache line size limitations with the libc++ mutex implementation?>> For libc++, it would probably need to be behind an ABI-breaking macro on Mac and FreeBSD, but we haven't committed to any ABI stability on Linux, so we could probably enable it by default there, and get into build bots. >> >> Maybe bring this up on the cfe-dev list to discuss with Marshall and other folks interested in libc++? > > On FreeBSD and OS X, the underlying pthread_mutex can already do deadlock detection, so I don't see why you'd need to add another word. The PTHREAD_MUTEX_ERRORCHECK attribute has been part of POSIX since 1997, so I'd expect it to be supported everywhere.Not every platform uses pthreads (such as Win32), so presuming that an underlying library will always support such functionality may not be the appropriate design decision. ~Aaron
On Sat, Jun 7, 2014 at 10:50 AM, Chandler Carruth <chandlerc at google.com> wrote:> > On Fri, Jun 6, 2014 at 10:57 PM, Kostya Serebryany <kcc at google.com> wrote: > >> As for the deadlocks, indeed it is possible to add deadlock detection >> directly to std::mutex and std::spinlock code. >> It may even end up being more efficient than a standalone deadlock >> detector -- >> but only if we can add an extra word to the mutex/spinlock object. >> The deadlock detector's overhead comes primarily from two tasks: >> 1. get the metadata for the lock in question. >> 2. query the lock-acquisition-order graph to see if there is a loop. >> >> If the lock-acquisition-order graph is sparse (99% of cases we've seen), >> then the task #1 may constitute up to 50% of the overhead. >> If we can add a word to std::mutex/std::spinlock data structures then the >> task #1 becomes trivial. >> > > I don't see any reason not to reserve a word in the mutex so that in (an > ABI-compatible) debug build the mutex can support deadlock detection. Some > people are super concerned about having an extra word in a mutex, but I'm > not at all. > > For libc++, it would probably need to be behind an ABI-breaking macro on > Mac and FreeBSD, but we haven't committed to any ABI stability on Linux, so > we could probably enable it by default there, and get into build bots. > > Maybe bring this up on the cfe-dev list to discuss with Marshall and other > folks interested in libc++? >Yes. I still have a debt with by vector annotations in libc++, let me deal with that first and then send a proposal about deadlock detector. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140609/ea8a3d55/attachment.html>
> > > On FreeBSD and OS X, the underlying pthread_mutex can already do deadlock > detection, so I don't see why you'd need to add another word. The > PTHREAD_MUTEX_ERRORCHECK attribute has been part of POSIX since 1997, so > I'd expect it to be supported everywhere. >PTHREAD_MUTEX_ERRORCHECK detects the deadlock that already happened. tsan's deadlock detector (as well as helgrind and many other similar tools) detects lock order inversion, i.e. a situation which may potentially lead to a deadlock. --kcc -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140609/ca54f5c5/attachment.html>