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

[Dean Sutherland]

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.