Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

SharC: Checking Data Sharing Strategies for Multithreaded C

Zachary Ryan Anderson, David Gay, Rob Ennals and Eric Brewer

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-25
March 27, 2008

http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-25.pdf

Unintended or unmediated data sharing is a frequent cause of insidious bugs in multithreaded programs. We present a tool called SharC (short for Sharing Checker) that allows a user to write lightweight annotations to declare how they believe objects are being shared between threads in their program. SharC uses a combination of static and dynamic analyses to check that the program conforms to this specification. SharC allows any type to have one of five ``sharing modes'' --- private to the current thread, read-only, shared under the control of a specified lock, intentionally racy, or checked dynamically. The dynamic mode uses run-time checking to verify that objects are either read-only, or only accessed by one thread. This allows us to check programs that would be difficult to check with a purely static system. If the user does not give a type an explicit annotation, then SharC uses a static type-qualifier analysis to infer that it is either private or should be checked dynamically. SharC allows objects to move between different sharing modes at runtime by using reference counting to check that there are no other references to the objects when they change mode. SharC's baseline dynamic analysis can check any C program, but is slow, and will generate false warnings about intentional data sharing. As the user adds more annotations, false warnings are reduced, and performance improves. We have found in practice that very few annotations are needed to describe all sharing and give reasonable performance. We ran SharC on 6 legacy C programs, summing to over 600k lines of code, and found that a total of only 60 simple annotations were needed to remove all false positives and to reduce performance overhead to only 2--14%.


BibTeX citation:

@techreport{Anderson:EECS-2008-25,
    Author = {Anderson, Zachary Ryan and Gay, David and Ennals, Rob and Brewer, Eric},
    Title = {SharC: Checking Data Sharing Strategies for Multithreaded C},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2008},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-25.html},
    Number = {UCB/EECS-2008-25},
    Abstract = {Unintended or unmediated data sharing is a frequent cause of insidious bugs in multithreaded programs. We present a tool called SharC (short for Sharing Checker) that allows a user to write lightweight annotations to declare how they believe objects are being shared between threads in their program. SharC uses a combination of static and dynamic analyses to check that the program conforms to this specification.

SharC allows any type to have one of five ``sharing modes'' ---  private to the current thread, read-only, shared under the control of a specified lock, intentionally racy, or checked dynamically. The dynamic mode uses run-time checking to verify that objects are either read-only, or only accessed by one thread. This allows us to check programs that would be difficult to check with a purely static system. If the user does not give a type an explicit annotation, then SharC uses a static type-qualifier analysis to infer that it is either private or should be checked dynamically.

SharC allows objects to move between different sharing modes at runtime by using reference counting to check that there are no other references to the objects when they change mode.

SharC's baseline dynamic analysis can check any C program, but is slow, and will generate false warnings about intentional data sharing. As the user adds more annotations, false warnings are reduced, and performance improves. We have found in practice that very few annotations are needed to describe all sharing and give reasonable performance. We ran SharC on 6 legacy C programs, summing to over 600k lines of code, and found that a total of only 60 simple annotations were needed to remove all false positives and to reduce performance overhead to only 2--14%.}
}

EndNote citation:

%0 Report
%A Anderson, Zachary Ryan
%A Gay, David
%A Ennals, Rob
%A Brewer, Eric
%T SharC: Checking Data Sharing Strategies for Multithreaded C
%I EECS Department, University of California, Berkeley
%D 2008
%8 March 27
%@ UCB/EECS-2008-25
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-25.html
%F Anderson:EECS-2008-25