Automatic identification of interesting interleavings in a multithreaded program

Abstract

A facility that for a multithreaded program executing on a root machine causes the threads of the program to be executed in a relative scheduling that produces an interesting result. The facility suspends execution of the program. The facility then tests a plurality of relative thread schedulings on one or more virtual machines and observes the result. Based upon the observed result the facility selects one of the tested relative thread schedulings. The facility then resumes execution of the program using the selected relative thread scheduling.

We claim: 
     
         1 . A method in a computing system that, for a multithreaded program executing on a root machine, causes the threads of the multithreaded program to be executed in a scheduling that produces an interesting result, the method comprising:
 suspending execution of all the threads of the multithreaded program on the root machine;   while execution of all the threads of the multithreaded program on the root machine are suspended, saving the state of the root machine;   performing a plurality of simulations, each simulation comprising:
 initializing a simulation machine with the saved state; 
 determining a set of communication interleavings among threads of the multithreaded program; 
 executing the multithreaded program on the simulation machine in accordance with the determined set of communication interleavings; and 
 attributing a single score to the simulation based on the results of execution of the multithreaded program; 
   selecting, based on a comparison of the attributed scores, one of the plurality of simulations; and   resuming execution of the multithreaded program on the root machine in accordance with the set of communication interleavings determined for the selected simulation.   
     
     
         2 . The method of  claim 1 , further comprising:
 storing a package containing the saved state and an indication of the set of communication interleavings determined for the selected simulation;   initializing a replay machine with the saved state from the package; and   executing the multithreaded program on the replay machine in accordance with the set of communication interleavings determined for the selected simulation indicated by the package.   
     
     
         3 . The method of  claim 1  wherein at least one of: the root machine and/or the simulation machine is a physical machine. 
     
     
         4 . The method of  claim 1  at least one of: the root machine and/or the simulation machine is a virtual machine. 
     
     
         5 . The method of  claim 1  wherein at least one of: the root machine and/or the simulation machine is a user-level process. 
     
     
         6 . The method of  claim 1  wherein executing the multithreaded program in accordance with the determined set of communication interleavings is performed by, for each of one or more threads of the multithreaded program, suspending execution of the thread at a point before it initiates a communication to another thread. 
     
     
         7 . The method of  claim 1  wherein executing the multithreaded program in accordance with the determined set of communication interleavings is performed by, for each of one or more threads of the multithreaded program, delaying delivery of the communication to another thread initiated by the thread. 
     
     
         8 . The method of  claim 1  wherein communication interleavings include memory access interleavings. 
     
     
         9 . The method of  claim 1  wherein the single score determined for each simulation reflects the extent to which the simulation's execution of the multithreaded program produces undesirable behavior. 
     
     
         10 . The method of  claim 1  wherein the single score attributed to at least one of the simulations of the plurality is based at least in part on an error reported by the simulation machine. 
     
     
         11 . The method of  claim 1  wherein the single score attributed to a selected simulation of the plurality is based, at least in part, on encountering a failed assertion in the execution of the multithreaded program during the selected simulation. 
     
     
         12 . The method of  claim 1  wherein, for each of at least a portion of the plurality of simulations, determining a set of communication interleavings for the simulation comprises:
 determining an order in which thread communications were performed during execution of the multithreaded program in a previous simulation; 
 identifying at least one possible reordering within the determined thread communications order; 
 selecting one of the identified possible reorderings; and 
 determining a set of communication interleavings that incorporates the identified reordering. 
 
     
     
         13 . The method of  claim 12  wherein the identification of possible reorderings identifies a proper subset of all possible reorderings that are functionally distinct. 
     
     
         14 . The method of  claim 13 , further comprising, for each of the plurality of simulations, maintaining clock vectors for each thread of the multithreaded program that are used as a basis for identifying reorderings among the possible reorderings that are functionally distinct. 
     
     
         15 . The method of  claim 12  wherein the selection of one of the identified possible reorderings is based at least in part on the extent to which each of the identified possible reorderings relates to a portion of the code of the multithreaded program explicitly identified by its developer. 
     
     
         16 . A method for causing threads of a multithreaded program executing on a root machine to be executed in a relative scheduling that produces an interesting result, the method comprising:
 suspending execution of all the threads of the multithreaded program;   for each selected relative thread scheduling of a plurality of relative thread schedulings:
 performing a test of the selected relative thread scheduling on one or more virtual machines; and 
 observing the result of the test; 
   attributing a score to each test based on an extent to which the test identified undesirable behavior;   based on a comparison between the various scores attributed to each of the tests, selecting one of the tested relative thread schedulings; and   resuming execution of the multithreaded program using the selected relative thread scheduling.   
     
     
         17 . The method of  claim 16  wherein testing at least one of the plurality of relative thread schedulings comprises executing through an interrupt to an interrupt handler. 
     
     
         18 . The method of  claim 16  wherein testing at least one of the plurality of relative thread schedulings comprises executing through a physical device access. 
     
     
         19 . The method of  claim 16  wherein testing at least one of the plurality of relative thread schedulings comprises executing through a logical device access. 
     
     
         20 . A method for collectively storing, in one or more memories, a data structure relating to a multithreaded program whose threads each access memory locations, the method comprising:
 selecting, from among multiple observed orders of communication interleavings, a prescribed order of communication interleavings,
 wherein each observed order of communication interleavings of the multiple observed orders of communication interleavings indicates, for each selected memory location of one or more memory locations, an order in which the threads accessed the selected memory location during a previous execution of the multithreaded program corresponding to that order of communication interleavings, 
 wherein each of the multiple observed orders of communication interleavings is associated with a score indicating an extent to which the corresponding previous execution of the multithreaded program was interesting, and 
 wherein the selection of the prescribed order of communication interleavings is based on the score associated with the prescribed order of communication interleavings indicating that the prescribed order of communication interleavings resulted in the most interesting result; and 
   storing, in the memories, an indication of the selected prescribed order of communication interleavings;   
       wherein:
 the contents of the data structure can be used to reproduce the most interesting result in a virtual machine other than the distinguished virtual machine.