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 <[email protected]>wrote: > On Jun 20, 2013, at 7:12 PM, Delesley Hutchins <[email protected]> > 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 | [email protected] | 505-206-0315
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
