[LLVMdev] Multi-threading and mutexes in LLVM

[Kostya Serebryany]

On Sat, Jun 7, 2014 at 5:47 AM, Zachary Turner <zturner at google.com> wrote:

> +chandlerc, aaronballman, in case there are additional carryovers and/or
> issues from the review thread which I've left out.
>
>
> I have a patch up for review[1, 2] that attempts to replace LLVM's mutex
> implementation with std::mutex and std::recursive_mutex.  While the patch
> seems to work, there are questions surrounding whether or not the approach
> used is correct.
>
> I'll try to summarize the issues as best I can, in hopes of getting some
> feedback from a broader audience, to make sure this is done correctly:
>
> 1) Should support multi-threading be a compile-time or runtime parameter
> in LLVM?
>
> Currently it is both.  It is compile-time through the use of the
> define LLVM_ENABLE_THREADS, and it is runtime through the use of functions
> llvm_start_multithreaded, llvm_is_multithreaded, etc.  I and some others
> feel like runtime support for multi-threading could be removed, and it
> should be compile-time only.  However, I am not aware of all the ways in
> which this is being used, so this is where I would like some feedback.  The
> issues I have with runtime multithreading support are the following:
>
> * It leads to confusing code.  At any given point, is multi-threading
> enabled or disabled?  You never know without calling llvm_is_multithreaded,
> but even calling that is inherently racy, because someone else could
> disable it after it returns.
>
> * It leads to subtle bugs.  clang_createIndex, the first time it's called,
> enables multi-threading.  What happens if someone else disables it later?
>  Things like this shouldn't even be possible.
>
> * Not all platforms even support threading to begin with.  This works now
> because llvm_start_multithreaded(), if the compile time flag is set to
> disable threads, simply does nothing.  But this decision should be made by
> someone else.  Nobody really checks the return value from
> llvm_start_multithreaded anyway, so there's already probably bugs where
> someone tries to start multi-threading, and it fails.
>
> * What does it actually mean to turn multi-threading support on and off?
>
> Anybody that tries to do this is almost certainly broken due to some edge
> cases about when it's on and when it's off.  So this goes back to the first
> two points about confusing code and subtle bugs.
>

+1
I am in favor of removing the run-time check. We've seen lots of code like
this "if (have_threads) mu->lock();", and it was very often broken.


>
> 2) What should happen when you try to acquire a mutex in an app with
> threading disabled?
>
> If this is a compile-time parameter, the solution is simple: make an empty
> mutex class that satisfies the Lockable concept, and have its methods do
> nothing.  Then typedef something like llvm::mutex to be either std::mutex
> or llvm::null_mutex accordingly.  If this is a runtime parameter, it's more
> complicated, and we should ask ourselves whether or not it's necessary to
> avoid the overhead of acquiring an uncontended mutex in single threaded
> apps.  For what it's worth, all reasonable STL implementations will use a
> lightweight mutex implementation, which generally require less than 100
> nanoseconds to acquire uncontended, so I think we don't need to care, but
> again some feedback would be nice.
>
> 3) We have some debug code in our mutex implementation that is intended to
> try to help catch deadlocks and/or race conditions.  Do we need this code?
>
> I think we can get by without it, but again some feedback about how, if at
> all, people are using this would be nice.  For example, if you want to
> detect deadlocks and race conditions you can use TSan.
>

The problem with race detection is that it slows down the process, but I
doubt that a debug code in mutex can catch (many) races.

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.
If we can't add a word for some reason, then I see no benefit from adding
debug mode directly to STL compared to a standalone deadlock detector.

(FTR: our deadlock detector in tsan:
https://code.google.com/p/thread-sanitizer/wiki/DeadlockDetector)

--kcc


>
> Thanks!
> Zach
>
>
> [1] -
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140602/220051.html
> [2] - http://reviews.llvm.org/D4033
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140607/02bf703f/attachment.html>