View source for COMP 3000 Essay 2 2010 Question 7

==Paper==
===[http://homeostasis.scs.carleton.ca/wiki/index.php/COMP_3000_Essay_2_2010_Question_7 Ad Hoc Synchronization Considered Harmful]===
Weiwei Xiong
University of California, San Diego

<b>Authors: </b>

Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou,

University of Illinois at Urbana-Champaign.

Zhiqiang Ma,

Intel.

==Research Problem==
As the computer industry continues to shift towards multicore processors, concurrent programming and the use of multithreaded designs has increased to keep up with this growing trend. Multithreaded applications can be found in a variety of popular applications today as they take advantage of the multithreaded approach. However, the concepts behind concurrent programming bring with them a host of potential dangers in the form of race conditions and deadlocks resulting from bad programming design and threads accessing shared memory. Fortunately, there are well known and standard methods for dealing with these problems, i.e synchronization primitives. But in real world situations, due to a variety of reasons, as we shall see, programmers often implement their own "ad hoc" synchronizations that eschew common design standards. Ad hoc synchronizations are not well documented and are not discovered by traditional tools for race conditions that look for standard synchronization primitives.

The paper we are discussing addresses these concerns in two regards, first it details a thorough study of ad hoc synchronizations. It details their nature, dangers, impact on bug detection tools and prevalence in several major open-source applications. Secondly, it introduces SyncFinder, a program that detects all ad hoc synchronizations and automatically annotates the source code where ad hoc sychnronizations are found. This can see use in conjunction with other data race checkers to improve accuracy and to build custom tools for finding deadlocks and bad programming practices. 

With detailed analysis of ad hoc synchronization and study of their occurrences in several applications, the research ultimately concludes that they are harmful and should be removed. At the same time, SyncFinder detects and documents ad hoc synchronizations in the source code enabling programmers for the first time to easily track and remove them.

==Background Concepts==

===Concurrent Programming===
Concurrent programming is a style of programming where multiple threads of execution run concurrently to perform a single task.  The thread of execution share a number of resources.  Particularly in multi-core processor systems and in distributed environments this style of programming can result in significant performance gains.  One significant challenge of concurrent programming is coordinating the different threads of execution, this is usually done using synchronization primitives.

===Synchronization Primitives===
Synchronization variables act as barriers to memory that prevent threads from accessing the same shared resource concurrently<sup>[[#Foot8|8]]</sup> and facilitate coordination between different threads. They come in many forms such as locks, mutexes, semaphores, and condition variables.
Locks maintain access to data  and limit who has access when there are multiple threads. Examples of locks include read/write locks that only lock when a reader obtains the lock and latches, which unlock only after a specified number of threads have obtained them. 
Mutexes are mutually exclusive locks that threads employ to lock a resource that they need.  No other threads can access them at that point. Once they are finished, they release the lock and the other threads can then lock and access the resource.
Condition variables are variables that will block the thread until a certain condition is met. This allows the thread to only execute when it is safe to perform its operation.
Synchronization primitives can be misused and lead to a host of other problems generally referred to collectively as race conditions.

===Race conditions, deadlocks===
Race conditions are unintended side-effects of programming in concurrent systems, they occur when two or more processes have access to a shared resource and at least one of them has a write privilege. This leads to processes modifying the data that all processes share as others may be reading them and results in the reading of stale/incorrect data. They will occur during the execution of the program and often times are very difficult to detect and manipulate data in subtle ways. 

Deadlock is when two or more processes share a resource and each process is waiting on the other processes to unlock the resource. It becomes a circular chain and no process can continue.

Both these issues occur in concurrent programming and although there are no general solutions for deadlock<sup>[[#Foot9|9]]</sup>, there are suitable methods for dealing with them, and in the case of race conditions, using mutual exclusion locks and synchronization primitives can prevent race conditions. But no programmer is infallible and so there is always the issue of race conditions and deadlocks present in production code.

===Ad Hoc Synchronization===
Ad hoc synchronizations are loops called sync loops that continue until certain conditions are met via outside variables called sync variables. They are designed to control the flow of thread execution much like locking and unlocking resources. There can be multiple sync variables in a sync loop and they can have multiple exit conditions and dependencies. The diversity of the sync loops, their dependencies and execution paths leads to the difficulty in finding them.

==Contribution==

With concurrent programming commonly used in modern applications, we face many issues that result from having simultaneous execution. In order to maintain a concurrent system, synchronization is required to ensure that the executing tasks do not interfere with each other while avoiding potential race conditions. However, many programmers do not use proper synchronization primitives to deal with these issues. Rather, they implement synchronizations in an ad hoc fashion. The paper we are discussing shows that ad hoc synchronizations, though implemented as a solution to concurrency issues, are undesirable in a system. This paper details the characteristics of ad hoc synchronizations and the issues associated with this programming construct and introduces the program, SyncFinder, which is used to identify such synchronizations in code.

===Findings===

In order to identify the characteristics of ad hoc synchronizations, 12 mainstream programs were examined to find instances of ad hoc synchronizations. These programs were either of server, desktop or scientific type, including Apache, MySQL and Mozilla. Through manual inspection of the source code, these characteristics of ad hoc synchronizations were found.

1. In all programs studied, it was found that each contained numerous ad hoc synchronizations. The number of synchronizations found ranged from 6-83, with server type programs inhabiting the higher portion of the interval. It is likely that programmers use this type of synchronization for two reasons. 
* In order to ensure a certain order of execution in the case of a concurrent system, programmers will use ad hoc synchronization to superimpose this order. With traditional synchronization techniques, this can vary between systems. As the order can vary, it is difficult to create a common interface.
* Some synchronization techniques introduce heavy-weight synchronization primitives. As such, programmers will use ad hoc synchronizations to avoid this and supposedly protect performance.

2. Often, it is very hard to identify an ad hoc loop as a synchronization method. They are hard to distinguish from other computational loops and as the implementations are diverse, it is hard to pinpoint them from the code. This can make the system hard to maintain, as other programmers will not be able to identify ad hoc loops implemented by another and debugging programs cannot recognize them as issues. 

3. It was found that ad hoc synchronizations often introduce bugs into the system such as deadlocks or hangs. As these are different than those caused by locks and other synchronizations it is hard for detection tools to recognize them if they were not first identified either manually or automatically. 

4. As they are not easily recognizable, it is hard for bug detection tools to fix issues presented by ad hoc synchronizations. In fact, it is often the case that these tools either do not find these issues or report them as false positives as the tool is unaware of the "work arounds" put into affect by using ad hoc synchronization. Since they cannot find these problems, it severely impacts the effectiveness of such tools.
This also impacts analysis of performance. Synchronization is quite costly and if a tool cannot recognize the form of synchronization, a false report is generated and the programmer will not be aware. This may cause poor decisions on the part of the programmer just from the fact that ad hoc synchronizations are hard to identify.

5. The reason ad hoc synchronizations are hard to identify stems from the fact that there is no single way of implementing them. Some typical characteristics of an ad hoc synchronization follow.
* These loops can contain one or multiple exit conditions. Some or all of these exit conditions may be satisfied by remote threads while others may be satisfied locally.
* Often, exit conditions depend on sync variables, variables that are shared with other tasks
* In some cases, the synchronization does not wait idly and rather performs other computations while checking the sync variables periodically.

Despite the dangers of using ad hoc synchronization, programmers continue to use this method. It is found that, in comments, programmers have stated that possibly their implementations are unsafe but proceed to use ad hoc synchronization techniques anyway. The reasoning behind these decisions have already been outlined in point 1. A better practice of synchronization would be to replace ad hoc synchronizations with synchronization primitives, primitives already present in standard POSIX thread libraries. However, it is often difficult to replace ad hoc synchronizations with synchronization primitives and doing this may not fulfill the concerns presented in point 1.

===SyncFinder===
SyncFinder is a tool built and designed by the authors of the paper for the purpose of identifying and annotating instances of ad hoc synchronization in concurrent programs built in C or C++.  The main goal of this was to aid programmers in better structuring their code, while simultaneously allowing for other tools to be utilized, recognizing them as synchronizations. It has demonstrated itself to be very effective in this area where other similar tools have failed, as it analyzes the code in a unique way that specifically tracks down sync loops that implement ad hoc synchronizations.
 
====How it works====
There are two possibilities to consider when searching for ad hoc synchronizations.  You can either analyze runtime traces via a dynamic method, or analyze the source code in a static method.  Both methods carry with them a number of pros and cons.  While a dynamic process is generally more accurate than a static method, it tends to accrue a very large runtime overhead.  In addition to this, the dynamic method is somewhat limited in which ad hoc synchronizations it can find by the code coverage of the test cases.  Taking these factors into consideration, the authors of the paper opted to pursue a static solution for achieving the goals set out for SyncFinder.  SyncFinder uses the LLVM compiler infrastructure.
 
1. Find Loops

An important commonality between all ad hoc synchronizations is that they are all caused by loops, be they “for”, “while” or “go to” loops.  These are generally referred to as "sync loops".  The first step in identifying sync loops is  The LLVM infrastructure is used to obtain the loop info from the source including a representation of the exit conditions.

2. Identify Sync Loops

The next and most important step is to differentiate between sync loops used for ad hoc synchronization and regular computational loops. It does this by going through the following steps:
* Exit Dependent Variable (EDV) Analysis: EDVs are variables that affect the exit conditions of a loop. A sync variable is a variable related to the synchronization of concurrent programs. Therefore, by identifying any EDVs as sync variables, it can be concluded that the loop is a sync loop. 
* Pruning Computational Loops: If a loop has at least one sync condition, it is considered a sync loop. Otherwise, it is pruned out as a computational loop.
* Pruning Condvar Loops: condvar loops are not considered sync loops. SyncFinder will go through all loop candidates and prune out any that calls cond_wait inside the loop.

3. Synchronization Pairing

The next step is to find the remote update that would release the sync loop. SyncFinder first finds all write instructions that would modify the sync variables. It then decides if the value that the write assigns to the sync variable would satisfy the exit condition. All those that do not are pruned. SyncFinder also prunes pairings that do not execute concurrently. This is done conservatively due to the limitations of static analysis.

4. SyncFinder Annotation

After the initial set of loops found is culled through the above process, the remaining loops are determined to be sync loops, and are suitably annotated.  Marking the source code with LLVM’s static instrumentation framework, it allows for other tools to take advantage of SyncFinder’s findings in their own analysis.

====Uses====
SyncFinder is a robust tool that can be utilized in a variety of applications such as bug detection, performance profiling and concurrency testing.  Using its auto-annotation feature, it is capable of identifying sections of code that demonstrate bad programming practices, which could in turn cause issues such as deadlocks.  In addition to this, the authors of the paper were able to expand upon the existing data race detector “Valgrind” in order to take advantage of the annotation system introduced by SyncFinder.  Through this, the authors were able to reduce the number of false positives flagged by the former, while being able to make use of the information it provides.

====Accuracy====
SyncFinder was tested against 25 concurrent programs that are used across a broad cross-section of applications.  In testing, SyncFinder was able to positively identify 96% of ad hoc synchronizations within the tested programs. False positives were at a rate of only 6%. In further tests, they were able to utilize SyncFinder’s auto-annotation systems to locate and mark 5 deadlocks and 16 potential issues within Apache, MySQL and Mozilla, that had previously been missed by other analysis tools.

====Related Work and similar tools====
There has been attempts to remove synchronization issues entirely from concurrent programming, such as transactional memory<sup>[[#Foot1|1]]</sup>, a lock-free synchronization that does not require mutexes, and avoids having to use lock, unlock operations. Other attempts have been made to remove bugs that would otherwise be safe from data races but are are still at risk of unintended effects from thread interactions, such as Atomizer<sup>[[#Foot2|2]]</sup>, a dynamic atomicity checker.

There are tools that detect data races such as CHESS<sup>[[#Foot3|3]]</sup>, a dynamic data race checker that runs through all possible thread execution paths and CTrigger<sup>[[#Foot4|4]]</sup>, a tool that checks for atomicity violations. The problem with these programs is that they only look for standard synchronization methods and structures, such as lock() and cond_wait(). They are not looking for ad hoc synchronizations.

A similar tool to SyncFinder exists that can detect simple spinning, also an ad hoc synchronization<sup>[[#Foot5|5]]</sup>, but it only detects simple spinning and not the more complicated ad hoc variations.

Several studies on bug characteristics<sup>[[#Foot6|6]]</sup> and concurrency bugs<sup>[[#Foot7|7]]</sup> have been composed. This paper complements these studies to better understand the nature of ad hoc synchronizations and their occurrence in concurrent programs.

==Critique==
===Style===
There is some unnecessary repetition in two sections of the essay, they list their findings from the study in the contribution section, but in the section that covers the characteristics of ad hoc synchronizations, they essentially repeat themselves with their previous findings. The two sections could have been combined.

===Evaluation===
The authors of the paper chose a mix of the leading concurrent open-source software programs<sup>[[#Foot10|10]]</sup> to base their study on. They were chosen to represent different uses of applications for server, desktop and scientific applications. The number of ad hoc synchronizations were determined by two authors who reviewed the source code themselves. They were both experienced with the code base, but mistakes could have been made. General conclusions would be hard to draw from the limited data set, but the study gives strong indicators of ad hoc synchronizations characteristics and their effects based on evidence from the software tested.

SynchFinder, the tool that the authors created has the benefit of a high degree of success, on average finding 96% of ad hoc synchronizations and can be extended to other data race and bad practice detector tools such as reducing Valgrind data race checker's false positives by 43%-86%. SynchFinder fills a niche where other tools have failed to detect ad hoc synchronizations before. On the downside SynchFinder produces 6% false positives. The false positives are due to lack of source code on library functions and incorrect pointer alias. But a programmer can then examine 
the returned ad hoc synchronizations to review them for false positives. It also requires source code of the application being tested but it was designed for programmers of the applications who have access. 
SynchFinder uses the static approach to finding ad hoc synchronizations by analyzing source code. A dynamic approach that uses run-time traces would be more accurate, but would carry a heavier computational load and would require a thorough run through of all possible test cases.

===Conclusion===
The paper's extensive examination of the previously unstudied ad hoc synchronizations concludes that they are prevalent in today's concurrent software, problematic and should be avoided. The basis of their study is well supported with diverse programs, but could always have used more.

SynchFinder is an effective tool for discovering ad hoc synchronizations with a high success rate and minimal requirements and bolster existing tools efforts at detecting bugs.

==References==
<span id="Foot1"><sup>1</sup> M Herlihy and J.E.B. Moss, 2NA0. Transactional Memory:
Architectural Support for Lock-Free Data Structures. [online] Available at: <http://www.cs.brown.edu/~mph/HerlihyM93/herlihy93transactional.pdf> [Accessed 23 November 2010].</span>

<span id="Foot2"><sup>2</sup> C Flanagan and S N Freund, 2NA0. Atomizer: A Dynamic Atomicity Checker For Multithreaded Programs (Summary). [online] Company(optional) Available at: <http://www.cs.williams.edu/~freund/papers/atomizer-padtad.pdf> [Accessed 23 November 2010].</span>

<span id="Foot3"><sup>3</sup> T Ball,M Musuvathi and S Qadeer, 2NA0. CHESS: A Systematic Testing Tool for Concurrent. [online] Company(optional) Available at: <http://research.microsoft.com/pubs/70509/tr-2007-149.pdf> [Accessed 23 November 2010].</span>

<span id="Foot4"><sup>4</sup> Park, Lu and Zhou, 2009. CTrigger: Exposing Atomicity Violation Bugs from Their Hiding Places. [online] University of Illinois at Urbana Champaign, Urbana, Available at: <http://pages.cs.wisc.edu/~shanlu/paper/asplos092-zhou.pdf> [Accessed 23 November 2010].</span>

<span id="Foot5"><sup>5</sup> LI, T., LEBECK, A. R., AND SORIN, D. J. Spin detection hardware for improved management of multithreaded systems. IEEE Transactions on Parallel and Distributed Systems PDS-17, 6 (June 2006), 508–521.</span>

<span id="Foot6"><sup>6</sup> Z Li, L Tan, X Wang, S Lu, Y Zhou, 2006. Have things changed now?: an empirical study of bug characteristics in modern open source software. Proc. of 1st Workshop on Architectural and System Support for Improving Software Dependability p.25-33 Available through CiteSeerX: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.6982> [Accessed 23 November 2010].</span>

<span id="Foot7"><sup>7</sup> Lu, Park, Seo and Zhou, 2010. Learning from Mistakes A Comprehensive Study on Real
World Concurrency Bug Characteristics.  [online] University of Illinois at Urbana Champaign, Available at: <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1203&amp;rep=rep1&amp;type=pdf> [Accessed 23 November 2010].</span>

<span id="Foot8"><sup>8</sup> John H. Baldwin , 2002. Locking in the Multithreaded FreeBSD Kernel. [online] FreeBSD Available at: <http://www.usenix.org/events/bsdcon/full_papers/baldwin/baldwin_html/node5.html> [Accessed 23 November 2010].</span>

<span id="Foot9"><sup>9</sup> Soma-notes, 2010. Basic Synchronization Principles. [online] Available at: <http://homeostasis.scs.carleton.ca/wiki/index.php/Basic_Synchronization_Principles> [Accessed 23 November 2010].</span>

<span id="Foot10"><sup>10</sup> BuiltWith, 2010. Apache Usage Statistics. [online] Available at: <http://trends.builtwith.com/Web-Server/Apache> [Accessed 30 November 2010].</span>