<div dir="ltr"><br><div>I understand that locks and roles are different in some sort of high-level cognitive sense.  However, I believe that the basic annotations and analysis are exactly the same; the difference lies only in how they are used.  In particular, you need to:</div>
<div><br></div><div>(a) Mark data as being protected by a lock/role.</div><div>(b) Mark functions as being protected by a lock/role.</div><div>(c) Identify when a thread acquires and releases a lock/role. </div><div>(c) Warn whenever a data/function is accessed/called without holding the proper lock/role.</div>
<div><br></div><div>Roles are globally defined, acquired on thread creation, and seldom or never released, while locks may be stored in objects and are much more fine-grained.  However, this indicates to me that roles are simply a subset of locks, not a completely different thing.</div>
<div><br></div><div>I very strongly believe that we should have one set of annotations, and one analysis for doing these checks.  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.<br>
</div><div><br></div><div><span style="font-family:arial,sans-serif;font-size:13px">> Thread role analysis operates on policy models such as "Only the GUI </span><span style="font-family:arial,sans-serif;font-size:13px">event thread may invoke [long-list-of-methods]."</span><br>
</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">Lock analysis establishes the same sort of policy.  You must hold 'lock' to call [long list of methods].</span></div>
<div><br></div><div><span style="font-family:arial,sans-serif;font-size:13px">> Section 5.2 of the PPoPP paper gives the full explanation.  In brief, it runs</span><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px">> off the idea that annotations are propagated from one function to another along</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">> the call graph.  Eg)</span><br>
</div><div><br></div><div><font face="arial, sans-serif">Lock annotations are propagated in exactly the same way.  The difference is that the current system does not infer missing annotations, so it will issue a warning instead:</font></div>
<div><br></div><div><div><span style="font-family:arial,sans-serif;font-size:13px">> void h() LOCKS_REQUIRED(mu_) {}</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">> void g() { h(); }  // warning -- missing LOCKS_REQUIRED(mu_) annotation</span></div>
</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">There are two reasons why I have not attempted to do inference yet.  First, inference requires whole-program analysis, which is incompatible with compiling by translation unit.  And second, with locks, it is impossible to determine whether the programmer is supposed to acquire mu_ within g(), or whether g() should be marked with LOCKS_REQUIRED.  With roles, you know that it's probably missing the annotation.</span></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">I propose a path forward to resolve these issues.</span></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">(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.  </span></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">(2) Implement role inference as a separate, whole-program analysis pass, using sidecar files etc.  I am willing to believe that role inference may be different from lock inference, although I'm not entirely convinced that the two cannot be merged.  But it seems to me that inference is what really distinguishes your work from the existing system, so let's put it in a separate tool.</span></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">(3) Reuse the current analysis as much as possible.  IMHO, it is always better to logically separate inference from checking; checking assumes a fully annotated program, while inference will infer missing annotations.  Your inference pass should thus supply the missing annotations, and then invoke the existing analysis to issue the warnings.  If the existing analysis needs to be extended, refactored, or fixed in some way in order to make this work, then let's do that; our goal is to keep the two analyses in sync.</span></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">> there does not appear to be enough similarity</span><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px">> to attempt to use the existing lock-based infrastructure as a jumping-off</span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">> point.</span><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></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">I completely disagree.  If one can be mapped into the other, as you yourself have said, then how are they not similar?</span></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">  -DeLesley</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jun 28, 2013 at 12:11 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 style="word-wrap:break-word">
TRA and the current thread safety checking seem to us to be different bike sheds, both of which are interesting.  For more, see below.
<div><br>
<div>
<div><div class="im">
<div>On Jun 24, 2013, at 2:19 PM, Chandler Carruth <<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>> wrote:</div>
<br>
<blockquote type="cite">
<div dir="ltr">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>
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><span style="color:rgb(34,34,34)">It may, in fact, be possible to combine the capabilities of TRA and</span><br>
</div>
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>
</blockquote>
<div><br>
</div>
<div>I will freely admit that I've not read all of this thread (it is *very* long, where possible brevity would be helpful to get a wider audience), I wanted to expand on the first email I sent to Aaron in response to this comment.</div>

<div><br>
</div>
<div><br>
</div>
<div>I think it is fundamentally important to approach contributing this type of work to clang as *incremental* improvements to the existing functionality. It would be very disruptive to the project to have a second analysis system surrounding thread safety.
 I'm not saying that the existing functionality is perfect or must be exactly preserved, I'm just saying that you should propose new functionality via an incremental path from where we are today.</div>
</div>
</div>
</div>
</blockquote></div>
[SNIP]<div class="im"><br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>I think these issues will (to a certain extent) be just as important as the concerns of basing this on sound academic research, and having a good theoretical model behind the analysis and diagnostics produced. As an example, I think one thing that is actively
 hurting the community in understanding your proposal is trying to first get an existing community to shift terminology to that of specific research papers, and then describing what you want in those terms. Maybe it would be possible to instead use the existing
 terminology, or where it isn't good terminology correct the terminology of the existing system before trying to describe new things in terms of it?</div>
</div>
</div>
</div>
</blockquote>
<br>
</div></div>
<div>The single biggest difference between the existing lock analysis and<br>
thread role analysis is that we're addressing different (but<br>
partly-overlapping) issues.<br>
<br>
Lock analysis starts with some data that must be protected from<br>
multi-threaded access.  You then annotate the data to indicate the<br>
specific lock that protects it, annotate methods to indicate how they<br>
interact with the locks.  Analysis involves tracking data references<br>
(which is the really hard part!) and then running the lock-set algorithm<br>
to make sure you never have an unprotected access. This is great stuff!<br>
This ensures that a program has correct and consistent use of locks and<br>
protection of data.<br>
<br>
Thread role analysis operates on policy models such as "Only the GUI<br>
event thread may invoke [long-list-of-methods]." This is a common<br>
idiom in many widely-used frameworks, for example AppKit's policy<br>
of always operating from the primary thread.  Many of these policies exist<br>
because fine-grained locking was too difficult, too expensive, or even<br>
impossible—perhaps due to deadlock potential—for the problem at hand.<br>
Other frameworks use a "no concurrency" model, outsourcing concurrency from<br>
the application to the framework. Although this serves to provide thread<br>
confinement of data, it also places restrictions on what *functions* may be<br>
invoked, independent of the *data* those objects may touch. For example: such<br>
code may never start a thread running, grab a thread from a pool, etc.  The</div>
<div>Actor design pattern provides an example of the "no concurrency in the </div>
<div>client" approach.</div>
<div><br>
Obviously, these two analyses are related. Policy-based concurrency<br>
sometimes serves as a proxy for lock-based concurrency. But policy-based<br>
concurrency is a subset of the use-case for TRA. When programmers know<br>
which thread roles may execute a particular function, this provides<br>
some guidance regarding what they can or should invoke from that<br>
function.  For example, an astronomy application we analyzed<br>
compartmentalized things like computation, printing, disk and network i/o,<br>
etc. onto individual threads.  This separation was partly for GUI<br>
responsiveness, performance and maintenance, all of which has limited<br>
relation to locking. The thread roles were purely a useful abstraction for<br>
enforcing developer policy.<br>
<br>
We feel that TRA and lock-based analysis are complementary, but<br>
different, systems that can benefit from each other.  There's nothing<br>
inherently disruptive about TRA to the overall architecture of clang<br>
(it's mostly making use of existing mechanisms); it can be implemented<br>
in an incremental fashion for easier community involvement.<br>
Ultimately, we believe there are considerable benefits to integrating<br>
the two systems together, but there does not appear to be enough similarity<br>
to attempt to use the existing lock-based infrastructure as a jumping-off<br>
point.</div><span class="HOEnZb"><font color="#888888">
<div><br>
</div>
<div>Dean Sutherland</div>
<div>(with much help from Aaron Ballman)</div>
<br>
</font></span></div>
</div>
</div>

</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>