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

[Delesley Hutchins]

I am dealing with a family emergency right now, so I apologize for being
somewhat brief.

> Every legal program in every programming language can be mapped into
assembly code...

To draw a different analogy that is perhaps somewhat more relevant to this
list than either asm or screwdrivers, there are many different languages
that can be mapped into LLVM IR.
Is LLVM an ideal IR for every language?  Obviously not.  It's too focused
on C/C++, has terrible GC support, no continuations, etc.  And yet, the
benefits of having a common compiler intermediate language are enormous
(reuse of optimization passes, back-ends, etc.)
As a result, many language implementers have chosen to work within the
limitations of the LLVM IR, even if it is not a perfect fit.

You and I seem to have fundamentally different goals here.  My goal is to
collaborate, and create a common analysis framework for thread safety.  I
would like to identify those areas where the existing framework is not
sufficient to meet your needs, and to extend the existing framework until
it does meet your needs.

Your goal seems to be to avoid collaboration.  If that is indeed your goal,
then perhaps a separate stand-alone tool or a clang plugin would be a more
suitable approach; that would give you much greater freedom to implement
your personal vision of what the analysis should look like.

  -DeLesley



On Sun, Jul 7, 2013 at 11:17 AM, Dean Sutherland <dsutherland at cert.org>wrote:

> I'd like to apologize to DeLesley and the list for the slowness of this
> response.  I wanted to take the time to provide a high-quality response, so
> as not to waste people's time.
>
> First an overall point that seems worthy of emphasis: Of course we intend
> to share as much with existing annotations and machinery as is plausible,
> diverging only where it makes sense.  Meanwhile, we appear to be wrestling
> over "where does it make sense to diverge?" After reading your feedback, it
> seems that I've succeeded in getting across the similarities between Thread
> Role Analysis (TRA, hereafter) and Lock Analysis (LA, hereafter), but I've
> failed to make the differences clear. That failure has led to a
> misunderstanding of the issues involved.
>
> This message focuses on two user-visible aspects of the analysis,
> regarding the annotations and use-cases.
> (1) Similarity in form isn't a good enough argument *by itself* to force
> similar things to be the same. Providing tools that match their expressive
> metaphor to the user's mental model *really matters* for adoptability. If
> this weren't true, we'd have only one programming language rather than many.
> (2) TRA and LA are optimized for different problems and express different
> mental models.
>
> Until we reach agreement on these user-visible issues, there's not much
> point in discussing implementation issues, so I'm deferring discussion of
> implementation issues to subsequent messages.
>
> ---
>
> 1. "Similar" is not "The Same:"
>
> On Jun 28, 2013, at 5:02 PM, Delesley Hutchins <delesley at google.com>
> wrote:
> > I completely disagree.  If one can be mapped into the other, as you
> yourself have said, then how are they not similar?
>
> Every legal program in every programming language can be mapped into
> assembly code; in this sense, all programing languages are "similar" both
> with each other and with assembly code. Nevertheless, we don't generally
> write programs in assembly code. Instead, we use abstractions that provide
> a better fit with our mental models of the problem at hand.
>
> On Jun 28, 2013, at 5:02 PM, Delesley Hutchins <delesley at google.com>
> wrote:
> > I do not want to introduce a second set of annotations that does exactly
> the same thing, or a second analysis that is almost like the first, but
> different in some subtle way.  That will only be confusing to people who
> are actually trying to use this stuff for practical programming.
>
> TRA annotations do not do "exactly the same thing" as the LA annotations.
> Right now, Clang has the lock-based analysis. Metaphorically, this is a
> screwdriver for slotted screws.  It has a handle, a shaft, and a flat
> blade; it's great for screwing in slotted screws.  We're proposing TRA; in
> this metaphor, call it a wood chisel.  We've told you that it has a handle,
> a shaft, and a flat blade; we've said that it's really good for squaring up
> mortices, but it can also screw in (some) slotted screws. Note that this
> description fails to emphasize differences such as blade width, blade
> sharpness, overall cross-section of the blade, etc. that matter a lot to
> each tool's primary use case.
>
> Without that detailed information, you've said, in essence, "but the
> screwdriver (with some small extensions) also works as a chisel for
> squaring up mortices." And, in a way, you're right.  You *can* use a
> screwdriver to square up a mortice. But you'd only want to substitute one
> tool for the other in an emergency. In spite of their similarities, a
> screwdriver makes a horrible chisel (and vice versa).
>
> The *reason* you don't want to substitute screwdrivers for chisels—or even
> just drop one tool or the other from your toolkit—is that each of these
> hand tools is carefully designed to be good at its primary task. That
> targeted focus is so important that nobody cares about their small overlap
> in function—except when you have only one and really needed the other.
>
> Partial similarity, in and of itself, is an insufficient reason to force
> tools into a single mold. Rather, it's more important to produce tools that
> are particularly good at their primary task.
>
>
> 2. Annotations, the user's mental model and expressive idioms, and how TRA
> and LA differ in focus:
>
> I realize that I've failed to adequately distinguish not only the primary
> tasks of the two analyses, but also the ways in which each analysis is
> carefully tuned for it's particular task. Because of that failure, I still
> need to convince you that the primary task of TRA differs in an interesting
> way from the primary task of LA.
>
> On Jun 28, 2013, at 5:02 PM, Delesley Hutchins <delesley at google.com>
> wrote (in part):
> > (1) Reuse the current annotations as much as possible.  If there are
> things that just can't be done with the existing annotations (you mentioned
> complex boolean conditions on roles), then let's come up with a minimal
> extension to support what you want to do.  I suspect that many such
> extensions would actually be valuable for locks as well.  Most of the
> existing annotations, GUARDED_BY, LOCKS_REQUIRED, etc. can be directly
> mapped onto your system, and can be re-used as-is.
>
> The annotation language for the lock analysis is carefully tuned for the
> particular kind of model we (e.g., analysis implementers) want its users to
> think about. Programmers already talk about properties like "this lock
> protects that data", "you must hold lock A before you call this method," or
> even "you must acquire lock B before you acquire lock C." The annotations
> used for lock analysis enable the user to directly express their mental
> model, using terms that closely reflect the language they already uses to
> discuss these issues. The TRA annotations could be upgraded to express
> these properties, but it would be a real struggle to express them as
> cleanly as do the lock annotations. Asking users to express locking in
> terms of thread roles would confuse the user by asking them to stretch a
> metaphor past the breaking point. The users are already thinking about
> locks, so matching the expression to their mental model is a good choice.
>
> The annotation language of TRA is also tuned for expressing the particular
> kind of model we want the users to think about. This model involves
> concepts programmers already talk about such as "call this method only from
> the GUI thread" or "Never do network I/O from a hard realtime thread" or
> even "Printing actions happen *only* on printing threads, stellar motion
> computation is limited to one of the Astronomy threads, insolation
> calculation happens only on *the* Insolation thread, and network I/O
> happens only on the background I/O threads". [That final, rather
> Baroque-sounding example is actually a cut-down; the original application
> had 27 distinct kinds of threads (e.g., thread roles), each with a
> different purpose. The author divided functionality across threads not only
> to provide a responsive user experience, but also to support separation of
> concerns and to simplify reasoning about timing.  But I digress.] These
> core use-cases for TRA don't involve locks at all. There may well be locks
> in the system (there virtually certainly are, in fact), but the users
> aren't thinking about locks in this context.
>
> Like locking analysis, TRA ensures that the as-written code matches the
> expressed model. However, it can also be used to answer questions such as
> "what kinds of threads may-execute this code segment?" In many systems,
> this knowledge provides useful guidance regarding actions that should (or
> shouldn't) be taken in that portion of the code. In combination with a
> good-enough effects/alias analysis TRA can also answer questions such as
> "which kinds of threads potentially access this data region?"  The answer
> to that question, in combination with some knowledge of application thread
> usage, can tell us which data regions require some form of concurrency
> control—probably locking.
>
> The annotations used for TRA enable the user to directly express their
> mental model, using terms that closely reflect the language programmers
> already use when discussing such issues. The LA annotations could be
> upgraded to express these properties, but it would be a real struggle to
> express them as cleanly as do the TRA annotations.  Asking users to express
> thread roles in terms of locking would be confusing because it would be
> asking them to stretch a metaphor past the breaking point. The users are
> already thinking about roles for threads and about how those roles interact
> with their code, so matching the expression to the user's mental model is a
> good choice.
>
> Both analyses encourage the user to form a mental model of some aspect of
> their program, capture that model in the form of annotations, and produce
> some useful analysis results regarding annotations and the as-written
> program. Any given aspect of the program could be described with a variety
> of models and annotations. One important goal for any analysis is to craft
> a model that not only sheds light on the problem being solved but also fits
> well with some part of how the programmer thinks about their program. TRA's
> annotations are different from the lock annotations specifically to
> distinguish them from the lock analysis in the user's mental model. Trying
> to use the TRA chisel in place of the lock analysis screwdriver (or vice
> versa) is *possible*. But the two analyses don't make very effective
> substitutes for each other; attempting to directly combine them would be
> likely to confuse end users.
>
> For example, suppose we have a program containing:
>
> void entry_point_of_hard_realtime_thread() {…}
>
> We'd like to enforce that only relevant code is invoked from the realtime
> thread.  Specifically, stalling the realtime thread for long periods (or
> perhaps even *at all*) would make it miss its deadlines, causing BAD THINGS
> to happen. So we wish to forbid method calls that might stall while
> executing on the realtime thread.
>
> Somewhere else in the program, we have:
>
> Foo *get_data_over_internet() {…} // reads from a socket internally;
>                                                                 // could
> stall for a long time
>
> It would obviously be a problem if get_data_over_internet() is ever
> invoked from the hard realtime thread.
>
> If you expressed this desired model using locking annotations, the hard
> realtime developers whose program inspired this example would ask "Why is
> there *ANY* mention of a lock here?" One of their first requirements for
> their realtime thread is "Never do ANYTHING that requires a lock from the
> realtime thread (with a very few carefully reviewed exceptions)."
> Programmers don't say "you must hold the realtime lock to call this method"
> or "never call this method while holding the realtime lock." Rather, they
> talk about "Never do network I/O from a hard realtime thread" or "this code
> could be executed by the realtime thread."
>
> > I do not want to introduce a second set of annotations that does exactly
> the same thing, or a second analysis that is almost like the first, but
> different in some subtle way.  That will only be confusing to people who
> are actually trying to use this stuff for practical programming.
>
> I have past experience that may shed light on the potential for confusion
> between these analyses when they are used for practical programming. The
> Fluid group's ensemble of analyses included TRA, Greenhouse's lock
> analysis, the Greenhouse/Boyland OO effects analysis, and several others.
>  End users were easily able to tell which analysis to use for various
> problems. If they were talking about data effects and ownership, they used
> the OO effects analysis. If they were talking about locks and data, they
> used the lock analysis. If they were talking about  "never do this from a
> that-flavored thread" they needed TRA. Over the course of years of case
> studies at dozens of sites with many developers and *millions* of lines of
> code, we never encountered the confusion you seem to be worried about. We
> did see endless cluelessness about concurrency, but that just gives us more
> evidence that concurrency-related analyses are important.
>
> Given these issues, I respectfully disagree with DeLesley's first point on
> moving forward.  Although the analyses are in some sense isomorphic, and
> could be forced into a single shared set of annotations, the metaphors
> programmers use to discuss the relevant properties are very different.
> Consequently, the annotations users write to express those properties
> should also be different so that the annotations will reflect the
> programmer's mental model. Squeezing both metaphors into a group of
> annotations aimed at only one of the two would be a bad fit.
>
> Once again, the entire discussion in this email is about user-visible
> issues. So far, we've said nothing about the underlying implementation
> issues. We will discuss those issues in subsequent email.




-- 
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/20130708/1f69f7fe/attachment.html>