Program tracing for time travel debugging and analysis

• US 10,042,737 B2
• Filed: 08/31/2016
• Issued: 08/07/2018
• Est. Priority Date: 08/31/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Mola, Jordi
• Primary Examiner(s): Mitchell, Jason D
• Application Number:
  US15/252,998
• Publication Number:
  US 20180060213A1
• Time in Patent Office: 706 Days
• Field of Search: 717128
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software

Abstract

Recording a replay-able trace of execution of a multi-threaded process includes identifying a trace memory model that defines one or more orderable events that are to be ordered across a plurality of threads of the multi-threaded process. The plurality of threads are executed concurrently across one or more processing units of one or more processors. During execution of the plurality of threads, a separate replay-able trace is recorded for each thread independently. Recording includes, for each thread, recording initial state for the thread, recording at least one memory read performed by at least one processor instruction executed by the thread that takes memory as input, and recording a least one orderable event performed by the thread with a monotonically increasing number that orders the event among other orderable events across the plurality of threads.

Claims

1. A computer system, comprising:

one or more processors; and

one or more computer-readable media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to record a replay-able trace of execution of a multi-threaded process, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following;

identify a trace memory model that defines one or more orderable events that are to be ordered across a plurality of threads of the multi-threaded process;

execute the plurality of threads concurrently across one or more processing units of the one or more processors; and

during execution of the plurality of threads, record a separate replay-able trace for each thread independently, including, for each thread;

recording initial state for the thread;

recording at least one memory read performed by at least one processor instruction executed by the thread that takes memory as input;

recording at least one orderable event performed by the thread with a monotonically increasing number that orders the event among other orderable events across the plurality of threads; and

recording a plurality of key frames for each of the plurality of threads, each of the plurality of key frames including information sufficient to enable the computer system to begin replaying the separate replay-able traces at execution locations that each correspond to a particular one of the plurality of key frames, wherein the plurality of key frames includes both a full key frame and a lightweight key frame, the full key frame including supplemental information in addition to the information needed to enable the computer system to begin replaying the separate replay-able traces at particular execution locations.

2. The computer system of claim 1, wherein recording initial state for the thread comprises recording an initial state of one or more processor registers prior to executing the thread.

3. The computer system of claim 1, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, recording the side effects of at least one non-deterministic processor instruction executed by the thread, including recording changes made by the non-deterministic processor instruction to one or more processor registers.

4. The computer system of claim 1, wherein recording at least one memory read performed by at least one processor instruction comprises recording the at least one memory read based on use of a prediction algorithm.

5. The computer system of claim 1, wherein recording at least one memory read performed by at least one processor instruction comprises using a shadow copy of memory that comprises only a subset of memory addressable by the process to predict a read value.

6. The computer system of claim 1, wherein recording at least one memory read performed by at least one processor instruction comprises recording the identity of a memory page associated with the memory read.

7. The computer system of claim 1, wherein the full key frame corresponds to a first replay-able trace, the supplemental information including header information of a loaded module.

8. The computer system of claim 1, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, determining that a memory read need not be recorded based on use of a prediction algorithm.

9. The computer system of claim 1, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, recording into one or more reusable ring buffers.

10. The computer system of claim 1, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, recording one or more interruptions to execution of the thread.

11. The computer system of claim 1, wherein a frequency of recording full key frames and lightweight key frames is adjustable.

12. A method, implemented at a computer system that includes one or more processors, for recording a replay-able trace of execution of a multi-threaded process, the method comprising:

identifying a trace memory model that defines one or more orderable events that are to be ordered across a plurality of threads of the multi-threaded process;

executing the plurality of threads concurrently across one or more processing units of the one or more processors; and

during execution of the plurality of threads, recording a separate replay-able trace for each thread independently, including, for each thread;

recording initial state for the thread;

recording at least one memory read performed by at least one processor instruction executed by the thread that takes memory as input;

recording a least one orderable event performed by the thread with a monotonically increasing number that orders the event among other orderable events across the plurality of threads; and

recording a plurality of key frames for each of the plurality of threads, each of the plurality of key frames including information sufficient to enable the computer system to begin replaying the separate replay-able traces at execution locations that each correspond to a particular one of the plurality of key frames, wherein the plurality of key frames includes both a full key frame and a lightweight key frame, the full key frame including supplemental information in addition to the information needed to enable the computer system to begin replaying the separate replay-able traces at particular execution locations.

13. The method of claim 12, wherein recording initial state for the thread comprises recording an initial state of one or more processor registers prior to executing the thread.

14. The method of claim 12, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, recording the side effects of at least one non-deterministic processor instruction executed by the thread, including recording changes made by the non-deterministic processor instruction to one or more processor registers.

15. The method of claim 12, wherein recording at least one memory read performed by at least one processor instruction comprises recording the at least one memory read based on use of a prediction algorithm.

16. The method of claim 12, wherein recording at least one memory read performed by at least one processor instruction comprises using a shadow copy of memory to predict a read value.

17. The method of claim 16, wherein the shadow copy comprises only a subset of memory addressable by the process.

18. The method of claim 12, wherein the full key frame corresponds to a first replay-able trace, the supplemental information including an identity of a loaded module.

19. The method of claim 12, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, determining that a memory read need not be recorded based on use of a prediction algorithm.

20. The method of claim 12, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, recording into one or more reusable ring buffers.

21. One or more hardware storage devices having stored thereon computer-executable instructions, the computer-executable instructions being executable by one or more processors of a computer system to cause the computer system to record a replay-able trace of execution of a multi-threaded process by causing the computer system to:

identify a trace memory model that defines one or more orderable events that are to be ordered across a plurality of threads of the multi-threaded process;

execute the plurality of threads concurrently across one or more processing units of the one or more processors; and

during execution of the plurality of threads, record a separate replay-able trace for each thread independently, including, for each thread;

recording initial state for the thread;

recording the side effects of at least one non-deterministic processor instruction executed by the thread;

recording at least one memory read performed by at least one processor instruction executed by the thread that takes memory as input;

recording a least one orderable event performed by the thread with a monotonically increasing number that orders the event among other orderable events across the plurality of threads; and

recording a plurality of key frames for each of the plurality of threads, each of the plurality of key frames including information sufficient to enable the computer system to begin replaying the separate replay-able traces at execution locations that each correspond to a particular one of the plurality of key frames, wherein the plurality of key frames includes both a full key frame and a lightweight key frame, the full key frame including supplemental information in addition to the information needed to enable the computer system to begin replaying the separate replay-able traces at particular execution locations.