Thread safety annotations and analysis in GCC

Thread safety annotations and analysis in GCC

[Le-Chun Wu]

[-- Attachment #1: Type: text/plain, Size: 976 bytes --]

Hi,

We have been working on creating program annotations for C/C++ (in GCC
attributes) to help developers document locks and how they need to be
used to safely read and write shared variables in multi-threaded code.
We've also implemented a new GCC pass that uses the annotations to
identify and warn about the issues that could potentially result in
race conditions and deadlocks. Here is the design doc for the proposed
annotations:

http://docs.google.com/Doc?id=ddqtfwhb_0c49t6zgr

Attached please find also find the patch file that contains the
initial implementation of the annotations and analysis.

Please let me know if you have any feedback/comments/questions on the
proposed annotations and the GCC implementation. We will be creating a
public branch for people who are interested to start contributing to
the project (before the patch is accepted and checked into the trunk).
We will send out another email once the public branch is created.

Thanks,

Le-Chun Wu

[-- Attachment #2: ts_annotations.patch.gz --]
[-- Type: application/x-gzip, Size: 35742 bytes --]

Re: Thread safety annotations and analysis in GCC

[Andi Kleen]

"Le-Chun Wu" <lcwu@google.com> writes:
>
> Please let me know if you have any feedback/comments/questions on the
> proposed annotations and the GCC implementation.

I was surprised that there was no consideration of C indirect function
calls in your design document. e.g. I would have expect some way
to give a hint that a indirect function call is always called from X
to propagate the lock sets. Right now it looks like they will
disable the analysis completely, correct?

-Andi

Re: Thread safety annotations and analysis in GCC

[Le-Chun Wu]

You are right that our current proposal/implementation doesn't handle
indirect function calls. (And we didn't try to do any pointer/alias
analysis for variables either in our first implementation .) But the
analysis will not be disabled completely if it encounters an indirect
function call. It simply ignores the indirect call. For example, when
analyzing function "foo" in the following code,

Mutex mu1, mu2;
int g GUARDED_BY(mu1);
void bar() EXCLUSIVE_LOCKS_REQUIRED(mu2);

int foo(int x, void (*indirect_func)())
{
  mu1.Lock();
  indirect_func();
  g = x + 2;
  mu1.Unlock();
}

main()
{
  foo(3, bar);
  ...
}

the analyzer will not be able to check the lock requirements for
"indirect_func", but it will continue to check whether writing to
variable "g" is indeed guarded by "mu1".

I think we tried to make the initial version of the
annotations/analysis simple so that users won't get too intimidated by
a very complex annotation system that covers all the cases. But
certainly it will be extended in the future. (Supporting the function
pointers/indirect calls is certainly one of the enhancements to
consider.)

Thanks,

Le-chun

On Mon, Jun 9, 2008 at 8:33 PM, Andi Kleen <andi@firstfloor.org> wrote:
> "Le-Chun Wu" <lcwu@google.com> writes:
>>
>> Please let me know if you have any feedback/comments/questions on the
>> proposed annotations and the GCC implementation.
>
> I was surprised that there was no consideration of C indirect function
> calls in your design document. e.g. I would have expect some way
> to give a hint that a indirect function call is always called from X
> to propagate the lock sets. Right now it looks like they will
> disable the analysis completely, correct?
>
> -Andi
>
>

Re: Thread safety annotations and analysis in GCC

[Tom Tromey]

>>>>> "Le-Chun" == Le-Chun Wu <lcwu@google.com> writes:

Le-Chun> Here is the design doc for the proposed annotations:
Le-Chun> http://docs.google.com/Doc?id=ddqtfwhb_0c49t6zgr

I am curious to know how this compares to the kind of lock checking
implemented in sparse, and in particular whether sparse annotations
could easily be translated to this style.

Tom

Re: Thread safety annotations and analysis in GCC

[Le-Chun Wu]

Tom,

Thanks a lot for pointing us to the sparse annotations. We will take a
look and see what its support looks like.

Le-chun

On Sun, Jun 15, 2008 at 2:43 PM, Tom Tromey <tromey@redhat.com> wrote:
>>>>>> "Le-Chun" == Le-Chun Wu <lcwu@google.com> writes:
>
> Le-Chun> Here is the design doc for the proposed annotations:
> Le-Chun> http://docs.google.com/Doc?id=ddqtfwhb_0c49t6zgr
>
> I am curious to know how this compares to the kind of lock checking
> implemented in sparse, and in particular whether sparse annotations
> could easily be translated to this style.
>
> Tom
>

Re: Thread safety annotations and analysis in GCC

[Ken Raeburn]

This looks like interesting work, and I hope something like this gets  
folded into a release soon.  A few things occurred to me when reading  
the writeup at google (sorry, I haven't started looking through the  
code much yet):

All the examples seem to be C++ oriented; is it, in fact, a goal for  
the annotations and analysis to be just as useful in C?

What are the scoping rules used for finding the mutex referenced in  
the GUARDED_BY macro within a C++ class definition?  Are they the same  
as for looking up identifiers in other contexts?  How is the lookup  
done for C structures?

Will the compiler get built-in knowledge of the OS library routines  
(e.g., pthread_mutex_lock) on various platforms?

You list separate annotations for "trylock" functions.  It appears  
that the difference is that "trylock" functions can fail.  However,  
pthread_mutex_lock can fail, if the mutex isn't properly initialized,  
if recursive locking of a non-recursive mutex is detected, or other  
reasons; the difference between pthread_mutex_lock and  
pthread_mutex_trylock is whether it will wait or immediately return  
EBUSY for a mutex locked by another thread.  So I think  
pthread_mutex_lock should be described as a "trylock" function too,  
under your semantics.  Conservatively written code will check for  
errors, and will have a path in which the lock is assumed *not* to  
have been acquired; if the analysis assumes pthread_mutex_lock always  
succeeds, that path may be analyzed incorrectly.  (I ran into a tool  
once before that complained about my locking code until I added an  
unlock call to the error handling path.  Since it's actively  
encouraging writing incorrect code, I'm not using it any more.)

Ken

Re: Thread safety annotations and analysis in GCC

[Le-Chun Wu]

Ken,

Thanks a lot for your feedback. Somehow your email fell through the
cracks and I didn't notice it until a colleague of mine reminded me.
Sorry for my delay in replying.

Here are my answers to your questions.

>
> All the examples seem to be C++ oriented; is it, in fact, a goal for the
> annotations and analysis to be just as useful in C?

It's true that we started out with a design more C++ oriented, but it
is also our goal to make the annotations and analysis useful in C. For
example, the original design of the annotations for lock/unlock
primitives didn't take any argument (as we assumed the primitives
would be member functions of a lockable class), but later we changed
the design to allow the annotations to take lock arguments for C-style
lock/unlock primitives.


>
> What are the scoping rules used for finding the mutex referenced in the
> GUARDED_BY macro within a C++ class definition?  Are they the same as for
> looking up identifiers in other contexts?  How is the lookup done for C
> structures?

The scoping rules for annotations on class members are the same as for
looking up identifiers in, say member functions. We modified GCC
front-end to process the thread-safety attributes after the class
definition is finished parsing so that we can reference in the
annotations data members declared later in the class. For example,
referencing "mu" in the GUARDED_BY annotation in the following example
is allowed:

class Foo {
  int a GUARDED_BY(mu);
  Mutex mu;
};

Unfortunately in our current implementation (on the thread-annotations
branch) we haven't modified the C front-end to support this. We will
do that soon.

>
> Will the compiler get built-in knowledge of the OS library routines (e.g.,
> pthread_mutex_lock) on various platforms?

Currently no. Users will need to provide declarations with the
annotations for these library routines in their code. e.g. they will
need to provide a declaration for pthread_mutex_lock like the
following:

int pthread_mutex_lock(pthread_mutex_t *mutex) EXCLUSIVE_LOCK_FUNCTION(1);

>
> You list separate annotations for "trylock" functions.  It appears that the
> difference is that "trylock" functions can fail.  However,
> pthread_mutex_lock can fail, if the mutex isn't properly initialized, if
> recursive locking of a non-recursive mutex is detected, or other reasons;
> the difference between pthread_mutex_lock and pthread_mutex_trylock is
> whether it will wait or immediately return EBUSY for a mutex locked by
> another thread.  So I think pthread_mutex_lock should be described as a
> "trylock" function too, under your semantics.  Conservatively written code
> will check for errors, and will have a path in which the lock is assumed
> *not* to have been acquired; if the analysis assumes pthread_mutex_lock
> always succeeds, that path may be analyzed incorrectly.  (I ran into a tool
> once before that complained about my locking code until I added an unlock
> call to the error handling path.  Since it's actively encouraging writing
> incorrect code, I'm not using it any more.)
>

Good point. pthread_mutex_lock should be annotated as a trylock
routine so that the analyzer won't emit (bogus) warning messages in
the code shown below (which is similar to what you referred to).

if (! pthread_mutex_lock(mu))
  {
    /* Do something */
    pthread_mutex_unlock(mu);
  }
else
  {
    /* Error handling */
    /* No need to unlock */
  }

(It also means that the declaration example I gave above for
pthread_mutex_lock should be changed. :-))

Thanks again for your feedback. Please let me know if you have any
other comments/questions (or bugs if you start to play with the
analysis pass).

Le-chun