Cache-based tracing for time travel debugging and analysis

• US 10,031,834 B2
• Filed: 11/11/2016
• Issued: 07/24/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): Dam, Tuan Q.
• Assistant Examiner(s): Wei, Zheng
• Application Number:
  US15/349,555
• Publication Number:
  US 20180060215A1
• Time in Patent Office: 620 Days
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

Recording a replay-able trace of execution of an executable entity using cache data includes executing one or more threads of the executable entity concurrently across one or more processing units of the one or more processors. During execution of the one or more threads, a separate replay-able trace is recorded for each thread independently. Recording includes, for each thread, recording initial processor register state for the thread. Recording also includes, for each thread, and upon detecting a processor data cache miss, recording at least one line of cache data imported into the processor data cache. Recording also includes recording the occurrence of at least one event by recording its side effects.

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 an executable entity using cache data, 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 events that are orderable across a plurality of threads of the executable entity;

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

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

recording initial processor register state for the thread; and

upon detecting a processor data cache miss based on execution of the thread, recording at least one line of cache data imported into the processor data cache in response to the processor data cache miss; and

during execution of at least one of the plurality of threads,

detecting an occurrence of a first event by the thread that should be recorded by its side effects of the first event, and recording the occurrence of the first event by recording the side effects of the first event into a replay-able trace for the thread, including recording one or more register values changed by the first event; and

detecting an occurrence of a second event by the thread that is one of the one or more events that are orderable, and recording the occurrence of the second event by recording a sequence identifier into the replay-able trace for the thread that orders the second event among other events that are orderable across the plurality of threads.

2. The computer system of claim 1, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one non-deterministic processor instruction.

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 at least one of:

an access violation, a trap, an interrupt, or a kernel call.

4. The computer system of claim 1, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one un-cached read.

5. The computer system of claim 1, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, detecting a processor code cache miss based on execution of the thread, and recording at least one line of cache data imported into the processor code cache in response to the processor code cache miss.

6. The computer system of claim 1, wherein recording at least one line of cache data imported into the processor data cache comprises recording the at least one line of cache data into a reusable ring buffer.

7. The computer system of claim 1, wherein the one or more processors set a hardware bit on a cache line based least on having recorded the at least one line of cache data for the thread, and toggle the hardware bit based upon an interrupt to execution of the thread by a kernel or by another thread.

8. The computer system of claim 1, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of an access to a model-specific register (MSR).

9. The computer system of claim 1, wherein recording a separate replay-able trace for each thread includes recording a plurality of entries into at least one replay-able trace out-of-order from an order in which the plurality of entries executed.

10. A method, implemented at a computer system that includes one or more processors, for recording a replay-able trace of execution of an executable entity using cache data, the method comprising:

identifying a trace memory model that defines one or more events that are orderable across a plurality of threads of the executable entity;

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

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

recording initial processor register state for the thread; and

upon detecting a processor data cache miss based on execution of the thread, recording at least one line of cache data imported into the processor data cache in response to the processor data cache miss; and

during execution of at least one of the plurality of threads,

detecting an occurrence of a first event by the thread that should be recorded by side effects of the first event, and recording the occurrence of the first event by recording the side effects of the first event Into a replay-able trace for the thread, including recording one or more register values changed by the first event; and

detecting an occurrence of a second event by the thread that is one of the one or more events that are orderable, and recording the occurrence of the second event by recording a sequence identifier into the replay-able trace for the thread that orders the second event among other events that are orderable across the plurality of threads.

11. The method of claim 10, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one non-deterministic processor instruction.

12. The method of claim 10, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, recording a change in flow control comprising at least one of:

an access violation, a trap, an interrupt, or a kernel call.

13. The method of claim 10, wherein recording a separate replay-able trace for each thread includes recording a plurality of entries into at least one replay-able trace out-of-order from an order in which the plurality of entries executed.

14. The method of claim 10, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, detecting a processor code cache miss based on execution of the thread, and recording at least one line of cache data imported into the processor code cache in response to the processor code cache miss.

15. The method of claim 10, wherein the one or more processors set a hardware bit on a cache line based least on having recorded the at least one line of cache data for the thread, and wherein the one or more processors toggle the hardware bit based upon an interrupt to execution of the thread by a kernel or by another thread.

16. The method of claim 10, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one of an access to a model-specific register (MSR) or an un-cached read.

17. The method of claim 10, wherein recording a separate replay-able trace for each thread independently, includes, for at least one thread, recording at least one of:

an un-cached read based on execution of the thread;

or

a Translation Lookaside Buffer (“

TLB”

) entry mapping a virtual memory addresses to a physical memory address.

18. A computer program product comprising one or more hardware storage devices 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 an executable entity using cache data, 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 events that are orderable across a plurality of threads of the executable entity;

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

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

recording initial processor register state for the thread;

upon detecting a processor data cache miss based on execution of the thread, recording at least one line of cache data imported into the processor data cache in response to the processor data cache miss; and

during execution of at least one of the plurality of threads,

detecting an occurrence of a first event by the thread that should be recorded by side effects of the first event, and recording the occurrence of the first event by recording the side effects of the first event into a replay-able trace for the thread, including recording one or more register values changed by the first event; and

detecting an occurrence of a second event by the thread that is one of the one or more events that are orderable, and recording the occurrence of the second event by recording a sequence identifier into the replay-able trace for the thread that orders the second event among other events that are orderable across the plurality of threads.

19. The computer program product of claim 18, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one non-deterministic processor instruction.

20. The computer program product of claim 18, wherein recording the occurrence of the first event by recording side effects of the first event comprises recording side effects of at least one un-cached read.