Adaptive granularity refinement in detecting potential data races

#The present invention relates generally to software. More specifically, adaptive granularity refinement in detecting potential data races is described.

#A data race is a type of problem that may occur in multi-threaded programs or multiple programs accessing the same data which may lead to anomalous behavior of the program(s). Data races may occur where a shared variable can be accessed by various threads/programs simultaneously. Threads/programs “race” to access a shared variable and, depending upon which access occurs first, program results may vary unpredictably. Conventional solutions to this problem attempt to detect data races before they occur. This is partially due to the fact that data races are unpredictable and thus extremely difficult to reproduce during the debugging process. Indeed, any anomalous behavior caused by a data race is dependent on the precise timing of separate threads/programs accessing the same memory location and may thus disappear if that timing is altered during the debugging process.

#Conventional solutions for data race detection monitor lock acquisition and memory accesses, computing an access pattern for each memory location and memory access. These solutions then evaluate the access pattern to memory locations to detect suspicious access patterns that may indicate a potential data race. An access pattern is “suspicious” if a memory location is shared among multiple threads without a common lock that may be used by individual threads/programs to govern access to the memory locations. Locks may be used to prevent data races from occurring where suspicious activity is detected.

#The foregoing summary, as well as the following detailed description of preferred embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there is shown in the drawings exemplary constructions of the invention; however, the invention is not limited to the specific methods and instrumentalities disclosed. In the drawings:

#FIG. 1 is an illustration of a conventional access pattern state diagram;

#FIG. 2 illustrates conventional encoding of access patterns;

#The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a computer-readable medium such as a computer-readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In general, the steps of disclosed processes may be performed in an arbitrary order, unless otherwise provided in the claims.

#A detailed description of one or more examples is provided below along with accompanying figures. The detailed description is provided in connection with such examples, but is not limited to any particular example. The scope is limited only by the claims and numerous alternatives, modifications and equivalents are encompassed. Numerous specific details are set forth in the following description in order to provide a thorough understanding. These details are provided for the purpose of example and the described techniques may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the examples has not been described in detail to avoid unnecessarily obscuring the description.

#Refinement of access pattern detection granularity from a whole-object (“object”) to an individual memory location may be performed by determining whether an access pattern that qualifies as a suspicious access pattern (“suspicious pattern”) has occurred on an object. If an access to an object is determined to have a suspicious pattern, then access pattern detection is granularly refined to individual memory locations within the object. Subsequently, the need for an extra storage space for each memory location is eliminated until an object access having a suspicious pattern is detected. By adaptively refining the granularity of access pattern detection, a single access pattern may be stored for objects that are not shared by individual threads of a multi-threaded program or multiple program or whose locking discipline is uniform for memory locations or fields within the object.