<div dir="ltr"><br><div>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.  </div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div><div>
<br></div><div>That said, you did point out some useful missing features, which are:</div><div><br></div><div><span style="font-family:arial,sans-serif;font-size:13px">> We support more complex boolean expressions over thread roles. The</span><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px">> existing Clang annotations cannot express multiple combinations of</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">> such properties.  For example, ((A & B & !C) | (D & !E)). </span><br>
</div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><font face="arial, sans-serif">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!</font></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">> </span><span style="font-family:arial,sans-serif;font-size:13px">TRA (for code) plus a sufficient effects and/or alias analysis (for</span></div>
<span style="font-family:arial,sans-serif;font-size:13px">> data) can combine to support discovery of data that *should* be locked</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">> (but currently is not).   .... </span><span style="font-family:arial,sans-serif;font-size:13px">Thus, multiple tricks to reduce the number of</span><div>
<span style="font-family:arial,sans-serif;font-size:13px">> annotations to </span><span style="font-family:arial,sans-serif;font-size:13px">be written (see the paper).  ... </span></div><div><font face="arial, sans-serif"><br>
</font></div><div><font face="arial, sans-serif">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.  </font></div>
<div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">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. </font></div>
<div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">The thing to be careful of here is that we will need to separate inference from checking, because there are three separate use cases:</font></div>
<div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">* Case 1: all annotations in source files.  (current system)</font></div><div><font face="arial, sans-serif">* Case 2: inference tool will add annotations to source files.  </font></div>
<div><font face="arial, sans-serif">* Case 3: inference tool will write annotations to sidecar files, to be used by separate analysis tool.</font></div><div><font face="arial, sans-serif"><br></font><div><br></div><div><br>
</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jun 21, 2013 at 1:31 PM, Dean Sutherland <span dir="ltr"><<a href="mailto:dsutherland@cert.org" target="_blank">dsutherland@cert.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Jun 20, 2013, at 7:12 PM, Delesley Hutchins <<a href="mailto:delesley@google.com">delesley@google.com</a>> wrote:<br>

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