[cfe-dev] [RFC] Adding Thread Role Analysis

[Delesley Hutchins]

<Continued, after accidental send>

Having the annotations in source files increases the annotation burden,
which makes it hard to apply the analysis to existing code.  On the other
hand, many of our users rely on explicit annotations as a form of
machine-checked documentation, making the thread policy explicit in the
code.  Case 2 is thus a good middle ground between the current system and
what you have proposed.  Moreover, once code has been annotated, further
checking can be done as part of the normal compile cycle, without having to
run a separate tool that does whole-program analysis.  I think all three
use cases should be supported.

  -DeLesley



On Mon, Jun 24, 2013 at 11:16 AM, Delesley Hutchins <delesley at google.com>wrote:

>
> Thank you for the long explanation.  However, based on what you've said, I
> do not think that your approach warrants a completely separate analysis,
> along with a completely separate set of annotations.
>
> In particular, I believe that "lock" and "role" are essentially the same
> thing.  In both cases, the analysis is marking functions and data
> structures as being "protected" by a particular lock/role, and ensuring
> that a thread must hold/have the lock/role before calling protected
> functions, or accessing protected data.  Most of the analysis logic
> (tracking lock/role sets, dealing with pointer aliasing, etc.) will thus be
> exactly the same.  It makes no sense to duplicate both annotations and
> logic.
>
> In particular, I foresee a time when someone might wish to use both locks
> *and* roles in the same program.  In that case, it would be much better to
> have a single analysis that understood both.
>
> That said, you did point out some useful missing features, which are:
>
> > We support more complex boolean expressions over thread roles. The
> > existing Clang annotations cannot express multiple combinations of
> > such properties.  For example, ((A & B & !C) | (D & !E)).
>
> As you mention, the existing analysis does not support this case.
>  However, this functionality would not be hard to add -- it's simply a
> boolean constraint on allowable lock sets.  If you feel it's valuable, then
> let's do that!
>
> > TRA (for code) plus a sufficient effects and/or alias analysis (for
> > data) can combine to support discovery of data that *should* be locked
> > (but currently is not).   .... Thus, multiple tricks to reduce the
> number of
> > annotations to be written (see the paper).  ...
>
> I would classify this under the heading of "annotation inference".  It
> would, indeed, be extremely useful to have a reliable way to infer the
> appropriate thread annotations.  There is an existing body of literature on
> thread inference for lock annotations, but it is currently completely
> unimplemented in clang; that would be a useful contribution.
>
> My general feeling is that role inference and lock inference will end up
> being very similar algorithms.  As you point out, however, there is a
> difference in scale -- there are at most a handful of roles in a program,
> while there may be many locks.  Thus, I am willing to be convinced that
> your inference algorithm for roles is faster and/or more complete than the
> corresponding version for locks, which would be reason for a separate
> implementation.
>
> The thing to be careful of here is that we will need to separate inference
> from checking, because there are three separate use cases:
>
> * Case 1: all annotations in source files.  (current system)
> * Case 2: inference tool will add annotations to source files.
> * Case 3: inference tool will write annotations to sidecar files, to be
> used by separate analysis tool.
>
>
>
>
>
>
>
>
>
>
>
>
>
> On Fri, Jun 21, 2013 at 1:31 PM, Dean Sutherland <dsutherland at cert.org>wrote:
>
>> On Jun 20, 2013, at 7:12 PM, Delesley Hutchins <delesley at google.com>
>> wrote:
>> >
>> > As Chandler mentioned, clang already has an existing thread safety
>> analysis,
>> > which is based on type systems for static race detection, which I
>> believe
>> > you are familiar with:
>> >
>> > http://users.soe.ucsc.edu/~cormac/papers/pldi00.pdf
>> > http://users.soe.ucsc.edu/~cormac/papers/toplas06-safe-locking.pdf
>> >
>> > The clang annotations can be found at:
>> > http://clang.llvm.org/docs/LanguageExtensions.html
>> >
>> > In a nutshell, the existing analysis allows a data member to be
>> annotated as
>> > being guarded by a particular lock.  Similarly, a function can be
>> annotated
>> > as requiring a particular lock to be held.  The analysis then tracks
>> the set
>> > of locks that are known to be held at every program point, and issues
>> > warnings when a data member is accessed or a function is called without
>> > holding the appropriate lock.
>>
>> We are familiar with these techniques, which are fundamentally similar to
>> the
>> lock analysis developed by our Fluid-group colleague Aaron Greenhouse
>> (see the
>> PPoPP paper's bibliography for references).  That said, we feel that TRA
>> has
>> additional benefits over the existing functionality.  The key difference
>> is
>> this: the Clang annotations, along with the vast majority of other work on
>> static analysis for thread safety, are focused on lock-based concurrency.
>> Thread role analysis is focused on NON-lock concurrency, which is a rather
>> different thing.  However, we realize that there can be overlap between
>> the two
>> techniques, for example with regards to enforcing reader-writer behavior.
>>
>> Thread role analysis doesn't concern itself with locks, which provides
>> benefits over the various lock-based analyses which don't do anything
>> when there's no locking involved.  The issues addressed are rather
>> different.  And, it turns out, many widely-used frameworks impose
>> thread usage policies on their clients.
>>
>> The easiest example to explain involves the typical threading model
>> used by most modern GUIs (including at least AWT/Swing and SWT in the
>> Java world, the X windowing system, and many others). Specifically:
>>
>> * There is at most one GUI event thread at a time. In some
>> implementations the identity of this thread is fixed. In others, the
>> identity of the GUI event thread may change from time to time.
>>
>> * The GUI does not use locks to protect its data structures. (Note:
>> this is from the *client* perspective.  There may be interesting
>> locking *inside* the GUI implementation, but this is typically hidden
>> from clients.) This choice was originally made for performance
>> reasons; it has persisted due to the clash between the need for
>> lock-ordering (to avoid deadlock) and the fact that events flow
>> bi-directionally between the GUI(and the user) on one side, and the
>> program and system on the other. This makes it extremely challenging
>> (and perhaps impossible) to create a single consistent lock-ordering.
>>
>> * The GUI must avoid race conditions, even though its data is
>> unprotected by locks. The typical solution is thread confinement, to
>> wit: *only* the GUI event thread may touch the GUI's data structures.
>> That's a thread usage policy, but not one that's easily expressable
>> using lock-based annotations.  The statements below are consequences
>> of that policy.
>>
>> * Code executing on threads other than the GUI event thread must never
>> invoke GUI methods (actually, most GUI methods; see below). Getting
>> this wrong breaks the necessary thread confinement. Note that this is
>> a transitive property which must be true for all code executing on
>> non-GUI threads.
>>
>> * GUI callback methods are invoked by the GUI on the GUI event thread,
>> even though it is client-written code.  Consequences include:
>> ** Code invoked from GUI callbacks must transitively invoke only
>> methods that can legitimately execute on the GUI event thread.
>> ** Data structures that are part of the client's UI implementation
>> inherit the thread-confinement policy from the GUI.
>> ** GUI callback methods should never be invoked from any thread
>> *other* than the GUI event thread.
>> ** All of these sub-items must be transitively true for all code
>> reachable from GUI callback methods.
>>
>> * Client code should avoid blocking the GUI event thread, because that
>> hangs the UI. Implications of this include:
>> ** Don't risk waiting on locks that may be held by another
>> thread. File and network I/O are probably a bad idea. Etc.
>> ** Don't kick off lengthy computations while executing on the event
>> thread.
>> ** All of these require the ability to "know" which code may be
>> executed by the event thread.
>> ** Once again, all of these sub-items must be transitively true for
>> all code reachable from GUI callback methods.
>>
>> * There are a few GUI functions that may be legitimately invoked from
>> any thread. This is typically a short list, at least when compared
>> with the total set of GUI framework methods. Typical examples include
>> adding and removing event listeners, requesting that some action be
>> taken on the GUI event thread (Swing calls this method
>> "invokeLater(...)", other GUIs have other names for it), etc.
>>
>> All of these properties are entirely policy-based.  The typical
>> lock-based concurrency analysis systems lack the concepts needed to
>> express or enforce them.  The concepts of thread roles and constraints
>> regarding which roles may execute which code (or touch which specific
>> data items, if data analysis is supported) enable simple expression
>> and enforcement of policies like these.
>>
>> > The existing analysis tracks locks, not threads or roles, so
>> > concepts like the "GUI thread" cannot be directly
>> > expressed. However, it's not hard to mimic this functionality -- the
>> > GUI thread acquires a lock named "GUI_lock" when it starts, and
>> > releases it when its done, and all code and data that should be
>> > GUI-only is annotated as requiring that lock.  (A lock in clang is
>> > simply a named C++ object; it does not need to implement an actual
>> > lock.)  Switching of roles can similarly be modeled as releasing one
>> > lock and acquiring another.  So at first glance, it seems to me that
>> > lock-based analysis is roughly similar to the analysis that you
>> > propose, and may in fact be significantly stronger; the "related
>> > work" section in your paper does not discuss the differences in much
>> > detail.
>>
>> It may be possible to squeeze TRA into the current thread safety
>> analysis by using "notional" locks in place of thread roles as you
>> suggest.  In what follows, a lock name (e.g., "A") means that the lock
>> is required; the negation of a lock name (e.g., "!A") means that it is
>> excluded.  The existing Clang annotations support requiring a set of
>> locks (e.g., (A & B & C) ) and also forbidding a set of locks
>> (e.g.,(!B & !C)).
>>
>> However, when you say:
>>
>> > and all code and data that should be GUI-only is annotated as
>> > requiring that lock.
>>
>> If this statement requires user-written annotations for all such
>> methods, the required annotation effort will make adoption exceedingly
>> difficult for most practicing programmers.  One of the benefits of TRA
>> is the application of well-founded techniques to avoid the need for
>> most user-written annotations.  Perhaps some of these techniques could
>> be brought to bear on the existing thread safety analysis.
>>
>>
>> TRA offers some additional capabilities:
>>
>>  * We support more complex boolean expressions over thread roles. The
>> existing Clang annotations cannot express multiple combinations of
>> such properties.  For example, ((A & B & !C) | (D & !E)).  Before you
>> ask, although such combinations would be nonsensical for locks, they
>> really do show up for thread roles in production code.
>>
>> * TRA allows statements that certain thread roles are mutually
>> exclusive (a GUI thread can't be a Compute thread, and vice
>> versa). The Clang annotations lack support for this property.
>>
>> * TRA (for code) plus a sufficient effects and/or alias analysis (for
>> data) can combine to support discovery of data that *should* be locked
>> (but currently is not), as well as demonstrating that notionally
>> thread-confined data is, in fact, thread confined.  If your existing
>> effects or alias analysis is strong enough, that's a really exciting
>> capability.  By comparison, the existing thread safety analysis
>> *starts* when you decide that you need to protect some data with a
>> lock.
>>
>> * TRA is strongly focused on reducing the user effort required to get
>> results.  Thus, multiple tricks to reduce the number of annotations to
>> be written (see the paper).  For example, our inference-based cross-TU
>> analysis avoids the need to annotate each method in a chain of calls
>> with the equivalent of a shared_locks_required() annotation. See also
>> the discussion in the paper of analysis of partially-annotated code,
>> "scoped promises" (NOT related to your scoped_lockable annotation),
>> and so on.
>>
>> Our experience with extensive field trials showed that pragmatic
>> adoptability requires all of:
>> * Sound results. The existing thread safety analysis is certainly
>> capably of providing this.
>> * A very smooth incremental adoption path. I believe that the existing
>> thread safety analysis provides this, for the properties it
>> addresses. At a minimum, you can work through an existing code-base
>> one lock at a time.
>>
>> * Very low programmer effort required to produce useful results.  My
>> past experience with lock-based analyses suggests that this is mixed.
>> The purely lock-based part is mostly there.  O-O effects and/or alias
>> analysis, however, mostly fails this test.  Particular challenges
>> arise due to the occasional need to prove properties like exclusive
>> ownership of heap data (for some cases), or more-precise effects than
>> "touches the heap" (for other cases).
>>
>> An important issue to be aware of is that the portion of a program
>> that needs to know about any particular lock (and the data item
>> protected by it) is typically a very small fraction of the total
>> program -- perhaps only a handful of methods.  Writing an annotation
>> for each method in that handful is rarely a substantial
>> burden. However, interesting programs may contain large numbers of
>> locks.
>>
>> Thread roles have very different properties. First, most programs --
>> even extremely large programs -- tend to involve only a handful of
>> interesting thread roles, regardless of the number of actual threads
>> at runtime.  The multi-million line programs we analyzed had fewer
>> than a dozen thread roles, but had thousands of threads.  During our
>> field testing, the largest number of distinct thread roles we
>> encountered in any one program was under 30.
>>
>> Secondly, interesting thread roles tend to involve very large swathes
>> of code.  For example, the GUI model described above essentially
>> partitions the entire program into two bins: GUI code and not-GUI
>> code. It should be obvious that although:
>>
>> > and all code and data that should be GUI-only is annotated as
>> > requiring that lock
>>
>> is exactly what we want conceptually, asking programmers to annotate
>> every method in the entire program is a guaranteed non-starter due to
>> the amount of effort required.  Hence our focus on extremely
>> light-weight annotations and extremely light-weight analysis (our goal
>> was less than double the compilation time of whatever we were
>> analyzing).  I believe that this tendency to be relevant to very large
>> fractions of an application is very different from the typical
>> use-case for the thread safety analysis, at least in terms of the
>> annotations to be written (or inferred).
>>
>> It may, in fact, be possible to combine the capabilities of TRA and
>> the current thread safety checking to produce something very
>> interesting.  Let's talk about it!  But we believe that TRA offers
>> sufficient benefits to warrant its inclusion as a feature in addition
>> to the existing lock-based analysis.  They're similiar in that they
>> both deal with thread safety, but solve the problem in different ways.
>>
>> > The existing clang annotations are used extensively on production
>> > code; we have many hundreds of thousands of lines that are currently
>> > annotated and checked.  It is not a research project.
>>
>> While the previous Java system described in the paper was a research
>> project, it has progressed far past that point.  It (along with
>> the other static analyses produced by members of the Fluid research
>> group) was used sucessfully on millions of lines of production Java
>> code (warts and all). The Fluid group's analyses (including TRA) were
>> subsequently tech-transferred out into industry.  In any case, the
>> Java side is definitely not research at this point.
>>
>> We're proposing to bring the same concepts over to the C-based family
>> of languages because the problems TRA solves are mostly
>> language-agnostic.  The extent of the research involved at this point
>> is in finding the most obvious ways to express the capabilities; the
>> underlying concept has already been proven useful and effective.
>>
>>
>
>
> --
> DeLesley Hutchins | Software Engineer | delesley at google.com | 505-206-0315
>



-- 
DeLesley Hutchins | Software Engineer | delesley at google.com | 505-206-0315
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130624/73662d54/attachment.html>