Proposal for thread safety attributes for Clang

The following is a proposal for a project we would like to contribute to Clang. Feel free to discuss.

Cheers,

Caitlin Sadowski
Google & University of California at Santa Cruz

Thread Safety Attributes for Clang

Summary

We would like to add a set of thread safety attributes to Clang. These attributes, based on a prior GCC implementation, will allow for checkable documentation of basic locking policies in multithreaded programs.

Background
The synchronization policies in modern multithreaded code may be poorly documented, and incorrectly inferred by new developers. Furthermore, when these policies are improperly followed they often lead to bugs which are difficult to reproduce and diagnose. One strategy for avoiding concurrency bugs is formal documentation of these synchronization policies. By writing this documentation using attribute-based annotations, Clang can mechanically check and warn about issues that could potentially result in race conditions and deadlocks.

Example

A code sample which demonstrates two of the proposed annotations is below. In this code sample, variables are protected by locks from the Mutex class. This class has been annotated to specify the API used to lock and unlock.

  • GUARDED_BY specifies a particular lock should be held when accessing the annotated variable. Violations of this locking policy may lead to data races.
  • ACQUIRED_AFTER annotations document the acquisition order between locks that can be held simultaneously by a thread, by specify the locks that need to be acquired before the annotated lock. Violations of this locking policy may lead to deadlocks.

1 #include “thread_annotations.h”
2 #define GUARDED_BY(x) attribute((GUARDED_BY(x)))
3 #define ACQUIRED_AFTER(x) attribute((ACQUIRED_AFTER(x)))
4
5 Mutex mu1;
6 Mutex mu2 ACQUIRED_AFTER(mu1);
7
8 int x GUARDED_BY(mu1);
9 int a GUARDED_BY(mu2);
10
11 void foo()
12 {
13 mu2.Lock();
14 mu1.Lock();
15 if (x > 2)
16 a = x + 1;
17 else
18 a = x - 1;
19 mu1.Unlock();
20 mu2.Unlock();
21 }

Sample compiler output:
ex.cc: In function ‘void foo()’:
ex.cc:12: warning: Lock ‘mu1’ is acquired after lock ‘mu2’ (acquired at line 14) but is annotated otherwise

Previous Work

As mentioned, thread safety annotations have been implemented in GCC. A full list of the annotations and descriptions for them can be found here:

http://gcc.gnu.org/wiki/ThreadSafetyAnnotation
https://docs.google.com/a/google.com/Doc?id=ddqtfwhb_0c49t6zgr

These annotations have been in active use in Google’s C++ codebase for a couple of years, so there is a large informal case study of their usefulness. The ideas behind many of these annotations come originally from a research paper [1].

Plan

We are planning to re-implement the GCC thread safety attributes in Clang. We will submit a series of patches to the cfe-commits mailing list. Our current plan for this serie is as follows:

  1. Basic parsing and semantic checking of the attributes which do not take arguments. In other words, checking whether the attribute is applied in the appropriate context (e.g. to a field, with no arguments).
  2. Basic parsing and semantic checking of the attributes which do take arguments, but without parsing or checking the arguments themselves. At this point, we will simply discard the tokens making up the arguments.
  3. Attribute argument parsing.
  4. Adding the thread safety analysis checks. We will teach the static analysis-based warnings layer to warn for violations of the annotations discussed on the links above.

Future Projects

Once we have this core set of thread safety annotations implemented, we have several directions for future work we would like to pursue. These include supporting additional types of annotations. For example, we would like to extend the system to support annotations for functions which only touch thread-local data and atomic functions which always execute as if they are not interleaved with operations of other threads. We would also like to build an annotation inference system; this system would enable application of the thread safety analysis to large amounts of legacy code.

[1] C. Flanagan and S. N. Freund. Type-based race detection for Java. In Programming Language Design and Implementation (PLDI), June 2000.

We have implemented a tool based on clang at Autodesk to help developers express their design decisions. The basic idea is the design decisions implemented as a set of customized GNU style attributes can serve as metadta to the fuctions, classes, etc and these metadata could be checked by clang static analyzer to enforce specific data access pattern and call graph for functions. We use this tool to help us parallelize some of our legacy C++ code base, for example, by enforcing a specific code is purely functinal style thus by definition is trivially thread safe.

Our implementation touches many pieces of clang as we don’t find a less intrusive way to get the attributes / metadata into clang’s type system and AST. As a result we have to periodically merge our code base with Clang official trunk, which sometimes is quite touch. The checker is easy to write as it is very well decoupled from the rest of the system.

I am wondering if this project would lead to an extensible annotation framework for Clang so user could encode arbitary metadata into Clang AST. That would be very useful and powerful for analysis code as it would involve develpers more intimately by capturing the design decisions eariler.

Cheers

~Michael

An extensible annotation framework would indeed be very useful. One
of my long-term goals for the project is to implement something along
the lines of "pluggable type systems", e.g.

http://portal.acm.org/citation.cfm?id=1167479
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9425&rep=rep1&type=pdf

in which various forms of static analysis could be implemented as
independent "type-checking" passes which make use of annotations in
the source code. Such a system would require an extensible annotation
framework, along the lines of what you are describing.

Our more immediate goal, of course, is to add support for a particular
set of annotations, and a particular form of analysis, which is
already used in a number of important projects here at Google. Once
that has been implemented, we can look at how best to generalize it.

  -DeLesley

Here is the first thread safety patch. Note that this patch depends on prior refactoring patches I sent out. If you want to review it, you can go to:

http://codereview.appspot.com/4667054

Cheers,

Caitlin

threadsafety_parsing_easyattrs.patch (16.6 KB)

Caitlin.

The two problems you address can be handled with templates instead of
annotations. While the techniques mentioned below do not solve all
thread-safety problems, they do solve the most common ones that I have
encountered. And none of them requires extensions to the compiler.

ACQUIRED_AFTER: Some deadlocks occur because you need to lock two
mutexes, A and B, and you accidentially lock A before B in one function
and B before A in another function. Such deadlocks can be avoided with
the Boost.Thread locking functions [1], as it guarantees that a list of
mutexes always is locked in the same order, regardless of the order you
list them.

GUARDED_BY: It is true that the C++ compiler does not know which mutex
guards what variables, and therefore cannot alert you if you, say, use
a variable without locking its mutex. I solved this problem in a
commercial project by defining two templates: a guard and an accessor.
The guard contained the mutex and the variable (or struct of
variables) as a private member, and only the accessor could access it.
The accessor would lock and unlock the mutex in a RAII manner. An
example using this technique could look like this:

   class Alpha
   {
   public:
     int GetValue() const
     {
       const_unique_access<int> value(valueGuard);
       return *value;
     }
     void SetValue(int v)
     {
       unique_access<int> value(valueGuard);
       *value = v;
     }
   private:
     unique_access_guard<int> valueGuard;
   };

This solution shares some traits with Anthony Williams' Synchronized
Values [2].

[1] http://www.boost.org/doc/libs/1_46_1/doc/html/thread/synchronization.html#thread.synchronization.lock_functions
[2] http://drdobbs.com/cpp/225200269

We have implemented a tool based on clang at Autodesk to help developers express their design decisions. The basic idea is the design decisions implemented as a set of customized GNU style attributes can serve as metadta to the fuctions, classes, etc and these metadata could be checked by clang static analyzer to enforce specific data access pattern and call graph for functions. We use this tool to help us parallelize some of our legacy C++ code base, for example, by enforcing a specific code is purely functinal style thus by definition is trivially thread safe.

Our implementation touches many pieces of clang as we don’t find a less intrusive way to get the attributes / metadata into clang’s type system and AST. As a result we have to periodically merge our code base with Clang official trunk, which sometimes is quite touch. The checker is easy to write as it is very well decoupled from the rest of the system.

I am wondering if this project would lead to an extensible annotation framework for Clang so user could encode arbitary metadata into Clang AST. That would be very useful and powerful for analysis code as it would involve develpers more intimately by capturing the design decisions eariler.

Cheers

~Michael

GUARDED_BY: It is true that the C++ compiler does not know which mutex
guards what variables, and therefore cannot alert you if you, say, use
a variable without locking its mutex. I solved this problem in a
commercial project by defining two templates: a guard and an accessor.
The guard contained the mutex and the variable (or struct of
variables) as a private member, and only the accessor could access it.
The accessor would lock and unlock the mutex in a RAII manner. An
example using this technique could look like this:

class Alpha
{
public:
int GetValue() const
{
const_unique_access value(valueGuard);
return *value;
}
void SetValue(int v)
{
unique_access value(valueGuard);
*value = v;
}
private:
unique_access_guard valueGuard;
};

Interesting idea - it has some parallels with a lambda-based more functional-programming inspired device similar to boost::optional I’ve been toying with. Using that type of technique you could do something like this:

uniquely_accessed value;

value.Access([](const int& i)
{

});

value.Mutate([](int& i)
{

});

Just as another take on the same construct.

Hi Chris,

I sent you a presentation which describes the project design and some of its implementation details, please check.

Also Francesco is collaborating with Vikram’s group at UPCRC to evaluate to use our tool as a base for the deterministic parallel C++ project (http://dpj.cs.uiuc.edu/DPJ/Future_Directions.html), which devises a set of annotations to document low level properties of functions in a more finely grained approach than our “high level” annotation of function properties like reentrancy. Francesco can provide more details if you are interested.

Cheers

~Michael

Bjorn,

There are many reasons why not to use templates for a similar thread
safety analysis. These issues include the fact that templates can
complicate the program, but may not be able to handle more complicated
locking scenarios. Given a particular locking strategy, the use of
templates forces the specification of that strategy to be closely tied
to the implementation details. If we wished to change how locking
works in a piece of code, the template system may not easily support
the new mechanism. Also, templates do not work for C code.

The attribute-based system provides an extensible way of supporting
future work, such as running more advanced analyses with the static
analyzer framework, new types of annotations that may be difficult to
implement with templates (such as cooperability yield points [1, 2]),
and annotation inference.

We have some evidence that this approach works well: we previously
implemented this proposal in GCC, and the use of attributes allowed us
to annotate large parts of Google's pre-existing codebase without
having to rearchitect it.

Cheers,
Caitlin

[1] Effects for Cooperable and Serializable Threads. Jaeheon Yi and
Cormac Flanagan. Workshop on types in Language Design and
Implementation (TLDI) 2010.
[2] Applying Usability Studies to Correctness Conditions: A Case Study
of Cooperability. Caitlin Sadowski and Jaeheon Yi. Onward! Workshop on
Evaluation and Usability of Programming Languages and Tools (PLATEAU),
2010.

Hey all,

Any other thoughts on this? Can we commit the first patch?

Also, here a fresh copy of the first patch, which fixes a name changed
since the time I initially emailed it out.

Cheers,

Caitlin

threadsafety_parsing_easyattrs_2.patch (16 KB)

Here is the first thread safety patch. Note that this patch depends on prior refactoring patches I sent out. If you want to review it, you can go to:

http://codereview.appspot.com/4667054

Hi Caitlin,

A few questions:

Summary

We would like to add a set of thread safety attributes to Clang. These attributes, based on a prior GCC implementation, will allow for checkable documentation of basic locking policies in multithreaded programs.

Are these in mainline GCC or just a branch? If they are in mainline GCC and have shipped in a release, then taking them into Clang makes sense for compatibility reasons. If they are a research project that is in development, then the bar to getting it into mainline clang is much higher, because adding attributes is tantamount to a language extension.

Plan

We are planning to re-implement the GCC thread safety attributes in Clang. We will submit a series of patches to the cfe-commits mailing list. Our current plan for this serie is as follows:

  1. Basic parsing and semantic checking of the attributes which do not take arguments. In other words, checking whether the attribute is applied in the appropriate context (e.g. to a field, with no arguments).
  2. Basic parsing and semantic checking of the attributes which do take arguments, but without parsing or checking the arguments themselves. At this point, we will simply discard the tokens making up the arguments.
  3. Attribute argument parsing.
  4. Adding the thread safety analysis checks. We will teach the static analysis-based warnings layer to warn for violations of the annotations discussed on the links above.

This sounds like a very reasonable breakdown. Please start with #0 though, which is “gain consensus that this is a good thing to take into mainline” :slight_smile:

I’m specifically concerned on a number of fronts here:

  1. Are these annotations general enough to apply to many common lock-based APIs?
  2. How do the annotations handle aliasing of lock objects?
  3. How many bugs have been found in practice?
  4. Have you considered doing this as a static analysis (where the bar is much lower to get things into mainline) instead of as a language change?

-Chris

Chris,

Are these in mainline GCC or just a branch? If they are in mainline GCC and
have shipped in a release, then taking them into Clang makes sense for
compatibility reasons. If they are a research project that is in
development, then the bar to getting it into mainline clang is much higher,
because adding attributes is tantamount to a language extension.

These annotations are in between the two extremes listed above. They
have gone beyond the initial research project stage, as they have
multiple years of use in production code.

They are currently not in mainline GCC (they are in a full-fledged
development branch). However, the only reasons for not including the
annotations in mainline GCC are the result of implementation concerns:
the GCC implementation involves invasive changes throughout the GCC
parser and depends on specific details of the lowering to GIMPLE. The
general consensus seems to be that the annotation system should be in
mainline GCC, after changing how they are implemented (unless Clang
gets there first).

I'm specifically concerned on a number of fronts here:
1. Are these annotations general enough to apply to many common lock-based
APIs?

The annotations themselves are general enough (the paper I cited
earlier actually contains an entire sound type-system based on a
subset of these annotations). Within the implementation, there are
tricky cases (like aliasing of lock objects) that lead to difficulties
in the application. However, our core synchronization libraries have
been successfully annotated, and it looks like less than 15% of
annotated code is impacted by these limitations.

2. How do the annotations handle aliasing of lock objects?

Right now they do not handle this. However, we would like eventually
support this feature.

3. How many bugs have been found in practice?

In a (relatively small) subsection of code at Google that has thread
safety annotations, I looked at one month of commit activity and found
18 bug-fixing commits (not including commits which just fix the
annotations) that cited these annotations explicitly as the way the
bug was found.

Also, the thread safety annotations are useful beyond just bug fixing.
At Google, the web search frontend team refused to write multithreaded
code until these thread-safety warnings were made available (through
that GCC branch) due to the number of bugs and difficulty of tracking
them down.

4. Have you considered doing this as a static analysis (where the bar is
much lower to get things into mainline) instead of as a language change?

The attribute system and the most fundamental analyses are things we
would like to see in the main compiler (after years of experience
successfully using these annotations in GCC). Plus, having this
starting point checked in will make it easier to build off and improve
the analysis. We are planning to have future analyses that build off
of these foundations start in the static analzyer.

Cheers,

Caitlin

To clarify one particular (but hopefully small) point…

It's worth noting that Rui Paulo was also working on at least a simple form of lock analysis for the static analyzer. Unfortunately my mail filters seemed to have thrown away some replies to my messages, so I only just responded to his latest patch. The subject line (on cfe-commits) is "PthreadLock Checker enhancements".

Jordy

Jordy/Rui,

Ah, interesting!

Of course, the two are somewhat orthogonal since the thread safety
attribute proposal is annotation-based (and hence are able to deal
with a larger set of issues).

Cheers,

Caitlin

Chris,

Any additional thoughts/questions?

Cheers,

Caitlin

Hello Caitlin,

By "static analysis-based warnings layer" are you referring to Sema's
CFG-base warnings, or a new checker for the static analyzer?

We are currently implementing the existing GCC checks with Sema's
CFG-based warnings. Future warnings and checks (e.g. which we do not
have a large amount of previous experience using) will start as
checkers in the static analyzer while they are being evaluated (and
only migrate into the compiler proper upon consensus).

Your first patch is fine to commit, with one addition: please also provide
documentation for the attributes you're adding (it's fine for it to be based
on the text in the C/C++ Thread Safety Annotations doc. you link to above),

Great! Thanks!

Cheers,

Caitlin Sadowski

First patch has been committed. Let me know if you had something
different in mind for the documentation. The second patch is attached
for review, also available at Issue 4707044: Finished basic parsing for all attributes - Code Review.

Cheers,

Caitlin

threadsafety_parsing_remainingattrs.patch (43.9 KB)

Second patch looks fine; please send future patches just to cfe-commits.

  - Doug