Cache-based tracing for time travel debugging and analysis

• US 10,031,833 B2
• Filed: 08/31/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): St Leger, Geoffrey
• Assistant Examiner(s): Wei, Zheng
• Application Number:
  US15/253,027
• Publication Number:
  US 20180060214A1
• Time in Patent Office: 692 Days
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program

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.

Claims

1. A computer system, comprising:

one or more processors, each including a corresponding processor data cache; 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 based on misses within a processor data cache, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following;

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

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

recording initial processor register state for a particular processing unit, of the one or more processing units, that is executing the thread;

upon detecting a cache miss within the particular processing unit'"'"'s corresponding processor data cache based on execution of the thread, recording at least one line of cache data imported into the corresponding processor data cache in response to the processor data cache miss;

detecting an occurrence of a discontinuity in execution of the thread, wherein one or more entries are imported in the corresponding processor data cache during the discontinuity in execution of the thread; and

based at least on the occurrence of the discontinuity in execution of the thread, flushing the one or more imported entries in the corresponding processor data cache, wherein the flushed entries are not recorded in the separate replay-able trace.

2. 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 side effects of at least one non-deterministic processor instruction executed by the thread.

3. The computer system of claim 1, wherein the one or more threads comprise a plurality of threads, the computer-executable instructions including instructions that are executable to cause the computer system to:

identify a trace memory model that defines one or more orderable events that are to be ordered across the plurality of threads,

wherein recording a separate replay-able trace for each thread independently, includes, for each thread, 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.

4. 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.

5. 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 un-cached read based on execution of the thread.

6. 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.

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

8. 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.

9. The computer system of claim 8, 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.

10. The computer system of claim 9, wherein the one or more processors toggle the hardware bit based upon the kernel or another thread having modified the cache line.

11. The computer system of claim 8, wherein setting the hardware bit prevents at least once cache flush when transitioning away from recording a thread.

12. The computer system of claim 8, wherein setting the hardware bit prevents at least one speculative memory access from being recorded to a trace.

13. The computer system of claim 1, wherein recording the replay-able trace for the thread includes recording a plurality of entries in the replay-able trace out-of-order from an order in which the plurality of entries executed.

14. The computer system of claim 1, wherein each cache line in the processor data cache includes at least one hardware bit that is toggled based at least on the cache line having been modified by a thread.

15. The computer system of claim 1, wherein detecting the occurrence of the discontinuity in execution of the thread comprises detecting at least one of:

execution of an operating system kernel, the occurrence of an interrupt, or the occurrence of an exception.

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

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

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

recording initial processor register state for a particular processing unit, of the one or more processors, that is executing for the thread;

upon detecting a cache miss within the particular processing unit'"'"'s corresponding processor data cache based on execution of the thread, recording at least one line of cache data imported into the corresponding processor data cache in response to the processor data cache miss;

detecting an occurrence of a discontinuity in execution of the thread, wherein one or more entries are imported in the corresponding processor data cache during the discontinuity in execution of the thread; and

based at least on the occurrence of the discontinuity in execution of the thread, flushing the one or more imported entries in the corresponding processor data cache, wherein the flushed entries are not recorded in the separate replay-able trace.

17. The method of claim 16, wherein recording a separate replay-able trace for each thread independently, includes, for each thread, recording one or more side effects of at least one non-deterministic processor instruction executed by the thread.

18. The method of claim 16, wherein the one or more threads comprise a plurality of threads, the method further comprising:

identifying a trace memory model that defines one or more orderable events that are to be ordered across the plurality of threads,

wherein recording a separate replay-able trace for each thread independently, includes, for each thread, 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.

19. The method of claim 16, 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.

20. The method of claim 16, wherein recording the replay-able trace for the thread includes recording a plurality of entries in the replay-able trace out-of-order from an order in which the plurality of entries executed.

21. The method of claim 16, 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 record at least one line of cache data imported into the processor code cache in response to the processor code cache miss.

22. The method of claim 16, 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.

23. The method of claim 22, wherein the one or more processors toggle a hardware bit based upon an interrupt to execution of the thread by a kernel or by another thread.

24. The method of claim 16, 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.

25. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors to cause a 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:

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

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

recording initial processor register state for a particular processing unit, of the one or more processing units, that is executing the thread;

upon detecting a cache miss within a processor data cache for the particular processing 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;

detecting an occurrence of a discontinuity in execution of the thread, wherein one or more entries are imported in the processor data cache during the discontinuity in execution of the thread; and

based at least on the occurrence of the discontinuity in execution of the thread, flushing the one or more imported entries in the processor data cache, wherein the flushed entries are not recorded in the separate replay-able trace.

26. A computer system, comprising:

one or more processors that comprise a cache memory; 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 in the cache memory, the computer-executable instructions including instructions that are executable to cause the computer system to perform at least the following;

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

during execution of the one or more threads, record a separate replay-able trace for each thread independently, including, for at least one thread;

recording into the trace initial processor register state for the at least one thread;

upon detecting a cache miss in the cache memory based on execution of the thread, recording into the trace a line of cache data imported into the cache memory in response to the cache miss;

based on recording the at least one line of cache data into the trace, setting a bit for the line of cache data in the cache memory;

after setting a bit for the line of cache data in the cache memory, detecting that another entity has subsequently written to the line of cache data in the cache memory;

based at least on the other entity subsequently writing to the line of cache data in the cache memory, clearing the bit for the line of cache data; and

based at least on clearing the bit for the line of cache data, flushing the line of cache data prior to further execution of the thread.