Efficient retrieval of memory values during trace replay

Preserving memory values during replay includes identifying trace sections that each represents events executed by an entity over a period of time. A parallel replay of trace sections is performed at a plurality of processing units. While performing the parallel replay, a persistence data structure corresponding to each trace section is maintained. This includes, for each trace section, storing, in the trace section's persistence data structure, a record of each memory address consumed by the processing unit while replaying the trace section, and a most recent memory value stored at each memory address. Returning a memory value during replay includes identifying relevant persistence data structures, and searching these data structures, in turn, based on a defined ordering. When a relevant memory address is identified during the search, the search is ceased and the value associated at the memory address, as stored in a persistence data structure, is returned.

BACKGROUND

When writing code during the development of software applications, developers commonly spend a significant amount of time “debugging” the code to find runtime and other source code errors. In doing so, developers may take several approaches to reproduce and localize a source code bug, such as observing behavior of a program based on different inputs, inserting debugging code (e.g., to print variable values, to track branches of execution, etc.), temporarily removing code portions, etc. Tracking down runtime errors to pinpoint code bugs can occupy a significant portion of application development time.

Many types of debugging applications (“debuggers”) have been developed in order to assist developers with the code debugging process. These tools offer developers the ability to trace, visualize, and alter the execution of computer code. For example, debuggers may visualize the execution of code instructions, may present code variable values at various times during code execution, may enable developers to alter code execution paths, and/or may enable developers to set “breakpoints” and/or “watchpoints” on code elements of interest (which, when reached during execution, causes execution of the code to be suspended), among other things.

An emerging form of debugging applications enable “time travel,” “reverse,” or “historic” debugging. With “time travel” debugging, execution of a program (e.g., executable entities such as threads) is recorded/traced by a trace application into one or more trace files. These trace file(s) can then be used to replay execution of the program later, for both forward and backward analysis. For example, “time travel” debuggers can enable a developer to set forward breakpoints/watchpoints (like conventional debuggers) as well as reverse breakpoints/watchpoints.

One challenge in implementing “time travel” debuggers involves how to return a memory value at a given point in a trace. One approach is to record a full copy of addressable memory of an executable entity at trace time, often using the same memory addresses that were seen by the executable entity at trace time. Then, replay involves loading this full memory copy, and performing memory reads and writes directly into it. Using this approach, reproducing memory values at a particular point involves reading the value from the memory copy. However, this approach produces prohibitively large amount of data at trace time (since a full copy of addressable memory is stored), and requires this large amount of data to be loaded at replay time. Furthermore, requiring maintenance of a large memory copy at replay time makes it impractical to perform parallel or speculative replay operations, and to store the values of memory at multiple particular points in time (for later retrieval).

Another approach is to replay code up to the last point that a memory address of interest was consumed prior to the point of interest in the trace, and return the value seen at that address. This has an advantage over the previous approach of using much less memory at replay time, but it introduces complexity and leads to poor performance for returning memory values, since a replay is performed in response to every request for a memory value.

BRIEF SUMMARY

At least some embodiments described herein preserve memory values during trace replay by maintaining plurality of persistence data structures during trace replay. Each persistence data structure corresponds to a different trace section of a trace, and stores the most recently seen value for each memory address encountered by that trace section. At least some embodiments herein also use the persistence data structures to return a memory value during trace replay. In these embodiments, returning a memory value involves progressively searching these persistence data structures—starting at the point of time of the requested memory value and going backwards until a persistence data structure storing the memory address of the requested memory value is encountered.

The foregoing embodiments provide advantages over prior approaches, including providing responsive performance for requests for memory values, while requiring a relatively small amount of memory information to be maintained during replay, and enabling low-cost mechanisms for storing the values of memory at multiple points in time.

For example, an embodiment of a method for preserving memory values during trace replay includes identifying, from among a plurality of trace data streams, a plurality of trace sections that each represents one or more events executed by an executable entity over a period of time. The method also includes performing a parallel replay of two or more of the plurality of trace sections at the plurality of processing units, including concurrently replaying each trace of the two or more trace sections at a different processing unit of the plurality of processing units. The method also includes, while concurrently replaying each trace section at a different processing unit, maintaining a different persistence data structure corresponding to each trace section. This includes, for each trace section, storing in the trace section's corresponding persistence data structure a record of each memory address consumed by the processing unit while replaying the trace section, and a most recent memory value stored at each memory address during replay of the trace section.

As another example, an embodiment of a method for returning a memory value during trace replay includes identifying, in a particular trace data stream, an event for which a memory value at a memory address associated with the event is requested. The method also includes identifying a defined ordering among a plurality of trace sections across a plurality of trace data streams that include the particular trace data stream. The method also includes identifying a plurality of persistence data structures that are each associated with a different trace section, and that occur prior to the location in the trace data stream based on the defined ordering. The method also includes identifying an ordering among the plurality of persistence data structures based on the defined ordering. The method also includes searching, in turn, and based on the identified ordering among the plurality of persistence data structures, one or more of the plurality of persistence data structures until the memory address is identified in a particular persistence data structure. When the memory address is identified in the particular persistence data structure, the method includes ceasing further searching of the plurality persistence data structures, and returning the value associated at the memory address, as stored in the particular persistence data structure.

DETAILED DESCRIPTION

At least some embodiments described herein preserve memory values during trace replay by maintaining plurality of persistence data structures during trace replay. Each persistence data structure corresponds to a different trace section of a trace, and stores the most recently seen value for each memory address encountered by that trace section. At least some embodiments herein also use the persistence data structures to return a memory value during trace replay. In these embodiments, returning a memory value involves progressively searching these persistence data structures—starting at the point of time of the requested memory value and going backwards until a persistence data structure storing the memory address of the requested memory value is encountered.

To the accomplishment of the foregoing,FIG. 1illustrates an example computing environment100that facilitates preserving memory values during replay of trace files, and efficient retrieval of those memory values. As depicted, embodiments may comprise or utilize a special-purpose or general-purpose computer system101that includes computer hardware, such as, for example, one or more processors102, system memory103, one or more data stores104, and/or input/output hardware105(e.g., such as the depicted keyboard/mouse hardware105a, networking hardware105b, and display device105c). In some embodiments, computer system101, and the components therein, could comprise a virtualized environment.

Embodiments within the scope of the present invention include physical and other computer-readable media for carrying or storing computer-executable instructions and/or data structures. Such computer-readable media can be any available media that can be accessed by the computer system101. Computer-readable media that store computer-executable instructions and/or data structures are computer storage devices. Computer-readable media that carry computer-executable instructions and/or data structures are transmission media. Thus, by way of example, and not limitation, embodiments of the invention can comprise at least two distinctly different kinds of computer-readable media: computer storage devices and transmission media.

Computer storage devices are physical hardware devices that store computer-executable instructions and/or data structures. Computer storage devices include various computer hardware, such as RAM, ROM, EEPROM, solid state drives (“SSDs”), flash memory, phase-change memory (“PCM”), optical disk storage, magnetic disk storage or other magnetic storage devices, or any other hardware device(s) which can be used to store program code in the form of computer-executable instructions or data structures, and which can be accessed and executed by the computer system101to implement the disclosed functionality of the invention. Thus, for example, computer storage devices may include the depicted system memory103, the depicted data store104which can store computer-executable instructions and/or data structures, or other storage such as on-processor storage, as discussed later.

Transmission media can include a network and/or data links which can be used to carry program code in the form of computer-executable instructions or data structures, and which can be accessed by the computer system101. A “network” is defined as one or more data links that enable the transport of electronic data between computer systems and/or modules and/or other electronic devices. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a computer system, the computer system may view the connection as transmission media. Combinations of the above should also be included within the scope of computer-readable media. For example, the input/output hardware105may comprise networking hardware105b(e.g., a hard-wired or wireless network interface module) that connects a network and/or data link that can be used to carry program code in the form of computer-executable instructions or data structures.

Further, upon reaching various computer system components, program code in the form of computer-executable instructions or data structures can be transferred automatically from transmission media to computer storage devices (or vice versa). For example, computer-executable instructions or data structures received over a network or data link can be buffered in RAM within networking hardware105b, and then eventually transferred to the system memory103and/or to less volatile computer storage devices (e.g., data store104) at the computer system101. Thus, it should be understood that computer storage devices can be included in computer system components that also (or even primarily) utilize transmission media.

Computer-executable instructions comprise, for example, instructions and data which, when executed at the processor(s)102, cause the computer system101to perform a certain function or group of functions. Computer-executable instructions may be, for example, binaries, intermediate format instructions such as assembly language, or even source code.

The data store104, which typically comprises durable storage, can store computer-executable instructions and/or data structures representing application code such as, for example, a trace record component106a, a trace replay component106b, an operating system107, and an application108(including portions of executable code108aof the application108). The data store104can also store other types of data, such as one or more trace file(s)109and persisted replay data110. When application code is executing (e.g., using the processor(s)102), the system memory103can store corresponding runtime data, such as runtime data structures, computer-executable instructions, etc. Thus,FIG. 1illustrates the system memory103as including runtime record/replay data106′ (including replay data structures106c), runtime operating system data107′, and runtime application data108′ (including runtime variables, data structures, etc. of application108as it executes, as well as runtime code portions108a′ which are in-memory copies of code portions108a).

The trace record component106ais usable to trace execution of an application, such as application108(including its executable code portions108a), and to store trace data in the trace file(s)109. In some embodiments, the trace record component106ais a standalone application, while in other embodiments it is integrated into another software component, such as the operating system107, a hypervisor, a debugging suite, etc. The trace record component106amay also exist at an entirely different computer system. Thus, the trace record component106amay trace execution of code at another computer system. Then, the trace file(s)109resulting from that tracing can be transferred (e.g., using the networking hardware105b) to the computer system101for replay by the trace replay component106b. While the trace file(s)109are depicted as being stored in the data store104, they may also be recorded exclusively or temporarily in the system memory103, or at some other storage device.

FIG. 1also includes a simplified representation of the internal hardware components of the processor(s)102. As illustrated, each processor102includes processing unit(s)102a. Each processing unit may be physical (i.e., a physical processor core) and/or logical (i.e., a logical core presented by a physical core that supports hyper-threading, in which more than one application thread executes at the physical core). Thus, for example, even though the processor102may in some embodiments include only a single physical processing unit (core), it could include two or more virtual processing units102apresented by that single physical processing unit.

Each processing unit102aexecutes processor instructions that are defined by applications (e.g., trace record component106a, trace replay component106b, operating system107, application code portions108a, etc.), and which instructions are selected from among a predefined processor instruction set architecture. The particular instruction set architecture of each processor102varies based on processor manufacturer and processor model. Common instruction set architectures include the IA-64 and IA-32 architectures from INTEL, INC., the AMD64 architecture from ADVANCED MICRO DEVICES, INC., and various Advanced RISC Machine (“ARM”) architectures from ARM HOLDINGS, PLC, although a great number of other instruction set architectures exist and can be used by the present invention. In general, an “instruction” is the smallest externally visible (i.e., external to the processor) unit of code that is executable by a processor.

Each processing unit102aobtains processor instructions from a shared processor cache102b(i.e., shared by the processing units102a), and executes the processor instructions based on data in the shared cache102b, based on data in registers102c, and/or without input data. In general, the shared cache102bis a small amount (i.e., small relative to the typical amount of system memory103) of random-access memory that stores on-processor copies of portions of the system memory103. For example, when executing the executable code portions108aof application108, the shared cache102bstores a subset of the runtime code portions108b′ in a code cache section of the shared cache102b, and stores other runtime application data108′ (e.g., variables, data structures, etc.) in a data cache section of the shared cache102b. If the processing unit(s)102arequire data not already stored in the shared cache102b, then a “cache miss” occurs, and that data is fetched from the system memory103(potentially evicting some other data from the shared cache102b). The registers102care hardware based storage locations that are defined based on the instruction set architecture of the processors(s)102.

The trace replay component106breplays one or more trace file(s)109by executing the code of the executable entity upon which the trace file(s)109are based at the processor(s)102, while supplying that code with traced data (e.g., register values, memory values, etc.) from the trace file(s)109at appropriate times. Thus, for example, the trace record component106amay record execution of one or more code portions108aof application108at the processor(s)102, while storing trace data (e.g., memory values read by code instructions, register values supplied code instructions, etc.) in the trace files(s)109. Then, the trace replay component106bcan re-execute the code portion(s)108aat the processor(s)102, while supplying that code with the trace data from the trace files(s)109so that the code is executed in the same manner that it was at trace time.

The trace replay component106balso maintains a plurality of persistence data structures that each store the most recent value of each memory address accessed (i.e., read from or written to) a corresponding trace section of the trace file109. This is described in connection with the detailed trace replay component200ofFIG. 2, and the environment300ofFIG. 3.

FIG. 2illustrates details of an example replay component200, such as the trace replay component106bofFIG. 1. As depicted inFIG. 2, the trace replay component200can include a number of sub-components, such as, for example, an identification component201, a replay component202, a persistence component203, a search component204, and/or a presentation component205. The depicted identity and arrangement of sub-components201-205are merely one example as an aide in description, and one of ordinary skill in the art will recognize that the particular identity and number of sub-components of the trace replay component200can vary greatly based on implementation.

The identification component201is responsible for identifying executable events in a trace file and memory locations of interest, for identifying trace sections of interest in order to obtain a memory value for a memory location of interest, for identifying an ordering among trace sections, and/or for identifying persistence data structures that are of interest for corresponding trace sections, etc. These concepts will be described in more detail herein after.

The replay component202performs trace replay operations, such as instructing one or more processing units102ato execute instructions from traced code portions108a, while supplying those code portions with data from a trace file109. As is described in more detail later in connection withFIG. 3, this may include instructing one or more processing units102ato perform reads from and/or writes to system memory103through a cache.

The persistence component203causes memory addresses and their corresponding values to be persisted to one or more persistence data structure(s) at various times during a trace replay. Persistence data structure(s) may, for example, be an in-memory replay data structure106c, or may be stored on disk (e.g., persisted replay data110). These persistence data structure(s) are then usable by the search component204to obtain desired memory values at specified times in the trace execution. These memory values can then be displayed using a presentation component205(e.g., such as at debugger user interface).

In the context ofFIGS. 1 and 2,FIG. 3illustrates an example environment300for preserving memory values during replay of trace files using a cache and persistence data structures. In particular, the embodiment300ofFIG. 3illustrates a replay component301(e.g., such as the trace replay component106bofFIG. 1and/or the trace replay component200ofFIG. 2) that causes read305aand/or write305boperations to be performed on a memory302(e.g., by a processing unit102aofFIG. 1). The memory302may comprise a portion of system memory103ofFIG. 1, such as runtime application data108′. In some embodiments, the memory302comprises a data structure maintained by the replay component301(e.g., such as one of the replay data structures106c) that reproduces the memory reads and/or writes actually observed during a trace. Thus, for example, the memory302may comprise a replay data structure106ccomprising an entire copy of memory that was addressable by the executable entity being traced, a cache data structure that reproduces the reads seen by the entity being traced, etc.

The memory302could include both memories storing the code of the executable entity (e.g., a code portion108a′) as well as operating memory used by the code of the executable entity. Thus, a read305aoperation may comprise a code read by a processing unit102athat obtains executable instructions from the memory302, and/or a data read by a processing unit102athat obtains runtime data (e.g., variables or other data structures) stored in the memory302. A write305boperation may comprise a data write that stores runtime data in the memory302. WhileFIG. 3depicts read305aand write305boperations, it will be appreciated that, when a memory access operation is accessing code data, a processor may treat the operation as an “execute” or a “fetch” operation. As used in this description and in the claims, a read305aoperation should be construed to comprise an “execute” and/or a “fetch” memory access operation in appropriate circumstances, such as when the operation is accessing code data.

As depicted inFIG. 3, the replay component301(e.g., replay component202) causes the read305aand write305boperations to be performed through a cache303. In general, the cache303operates in a similar manner to a processor cache (e.g., cache102bofFIG. 1), and in some embodiments it is in fact at least a portion of the processor cache102b(whether that be physical or virtualized). Thus, in general, the cache303stores a plurality of cache lines, each of which can be associated with a memory address (e.g., in system memory103), and store a cached copy of a portion of memory starting at that memory address and potentially spanning several memory addresses (depending on the size of the cache line).

FIG. 3also illustrates persistence data structures304, which includes a plurality of individual persistence data structures. For example,FIG. 3illustrates six individual persistence data structures304a-304f, though the ellipses indicate that persistence data structures304can include any number of individual persistence data structures. Depending on implementation, the individual persistence data structures may be each individually independent, or may be related in some way, such as part of a linked list, part of a hierarchical structure, indexed by a common hash table, etc. to make up the overall persistence data structure304.

In general, the persistence data structures304are used by the replay component301(e.g., using persistence component203) to store the values of memory addresses that are encountered by the code that is being replayed by the replay component202. Thus, the persistence data structures304are depicted as being connected to the replay component301via connection306aand/or the cache303via connection306b. The connection306bbetween the cache303and the persistence data structures304indicates that in some embodiments the persistence data structures304store evictions from the cache303. Thus, memory addresses/values that have been consumed by code is that being replayed are available either from the cache303(i.e., if it has been recently accessed) or from the persistence data structures304(i.e., if a memory address cached and then later evicted to the persistence data structures304).

The connection306abetween the replay component301and the persistence data structures304, however, indicates that replay component301can store memory addresses/values in the persistence data structures304using whatever scheme/rules it so chooses, and that the embodiments herein are not limited to storing cache evictions. For example, the persistence data structures304may store individual reads, including reads that would not make it into the cache303. Thus, in some implementations, the persistence data structures304stores memory addresses/values that correspond to reads that are considered un-cached by the processor architecture being used.

As indicated above, embodiments include storing individual persistence data structures (e.g.,304a-304f) that correspond to individual sections of a trace file109. To provide context for this concept,FIG. 4illustrates an example trace file400that enables separate replay of individual sections trace data streams and that, in turn, enables the creation of an individual persistence data structure for each section.

InFIG. 4, the trace file400independently stores a log of execution of each of a plurality of executable entities (e.g., different threads, different executable entities corresponding to different portions of executable code108aof the application108, etc.) that are executing in parallel. For example, inFIG. 4, the trace file400represents the execution of three parallel threads of an application, in which each parallel thread executed a different processing unit102aor processor102(including any combination of physical and/or virtual processing units/processors). Thus, inFIG. 4, the trace file400includes a separate data stream401for each processing unit102a/processor102—and thus for each executable entity of the application. The trace file400therefore includes three data streams401a-401c—but it could include any number of data streams401depending on a number of processing units102aavailable at the computer system101(whether they be in a single processor102or multiple processors102) and/or a number of executable entities created by the application108.

The data streams401may be included in a single file trace file109, or may each be stored in different files. Each data stream401includes data packets402storing trace data that is usable by the trace replay component301to reproduce execution of the corresponding executable entity, by supplying appropriate recorded state data (e.g., register values, memory addresses and values, etc.) to executable code of the executable entity at appropriate times. Thus, using the information in the data streams401, and using the actual executable code whose execution was traced, a full reproduction of execution of that code can be reproduced.

InFIG. 4, the data packets402are depicted as being separated by broken lines, and/or by key frames (which are discussed later). Thus, for example, three of the data packets in data stream401aare specifically identified as data packets402a-402c, and one of the data packets in data stream401bis specifically identified as data packet402d. As depicted, individual data packets402may be of differing sizes, depending on trace file implementation and on the particular data stored in each packet. Example data that may be included in a data packet includes information for identifying a code instruction executed, register values provided to that code instruction, memory addresses/values read, the side effects (e.g., resulting register values) of executing the code instruction, etc.

Using the format of trace file400, the trace record component106arecords each data stream401independently during parallel execution of the code being traced. As such, the timing of the executable events recorded by the trace record component106ainto data packets in one data stream is generally independent from the timing of the events recorded by the trace recoding component106ainto data packets in another data stream (while accounting for a general ordering based on orderable events, discussed below). Thus, the replay component203can replay sections of each data stream401independently and in parallel. For example, the ordering of the individual events in data packet402bare recorded separately from the individual events in data packet402d. As such, the events in these trace sections can be replayed independent from each other, even though they originally occurred in parallel.

The trace file400also stores sequencing events that record the timing and sequence of execution of certain events that are “orderable” across the data streams401. Orderable events may correspond to events by one thread that could affect execution of another thread, such as accessing shared memory. Thus, while the replay component202can generally replay each data stream401independently and in parallel, the orderable events to enforce a general ordering among sections of the traces. In some embodiments, orderable events are recorded using a sequencing number, comprising a monotonically incrementing number (“MIN”), which is guaranteed to not repeat. For example, the trace file400includes twelve sequencing numbers (depicted as circled numerals 1-12), each corresponding to the occurrence of different orderable events across data streams401a-401c.

Expanding on the example of the independence of data packets402band402d,FIG. 4also illustrates a first section404aof data stream401athat is bounded by sequencing numbers 1 and 4, and a second section404bof data stream401bbounded by sequencing numbers 2 and 6. While it is known that the orderable event at sequencing number 1 occurred before the orderable event at sequencing number 2, that the orderable event at sequencing number 2 occurred before the orderable event at sequencing number 4, and that the orderable event at sequencing number 4 occurred before the orderable event at sequencing number 6, the particular ordering of individual events in section404aversus the particular ordering of individual events in section404bis not known. As such, sections404aand404bcan be replayed in parallel with each other by the replay component202.

Orderable events may be defined according to a “trace memory model,” having defined orderable and non-orderable events that are used to identify how to store interactions across executable entities, such as threads. For example, orderable and/or non-orderable events may be defined based on how the threads interact through shared memory, their shared use of data in the shared memory, etc. Depending on implementation, a trace memory model may be weaker or stronger than a memory model used by the processor102. The trace memory model used may be a memory model defined by a programming language used to compile code (e.g., C++14), or some other memory model defined for purposes of tracing.

A first example trace memory model may treat as orderable only kernel calls (from user mode), traps, and exceptions. This trace memory model would have low overhead, since these operations are relatively “expensive” is their own right, they are likely tracked anyway and provide a very coarse grained overview of ordering. A second example trace memory model may treat as orderable full fences (i.e., operations that are have both acquire & release semantics). Examples of such operations may include INTEL's “locked” instructions, kernel calls, exceptions, and traps. This memory model would provide enough ordering for nearly all cross-thread communication that happens in the process when the code uses “interlocked” types of primitives to communicate cross threads, which is common in operating such as WINDOWS from MICROSOFT CORPORATION). A third example trace memory model may treat all acquires and releases as orderable. This memory model may be suitable for processors based ARM instruction sets, because ARM does not treat most loads and stores as acquires or releases. On other architectures, such as from INTEL (in which a majority of memory accesses are acquires or releases), this would equate to ordering almost all memory accesses. A fourth example trace memory model may treat as orderable all memory loads. This would provide for strong ordering but may lead to decreased performance as compared to the other example memory models. The foregoing memory models have been presented as examples only, and one of ordinary skill in the art will recognize, in view of the disclosure herein, there a vast variety of memory models may be chosen.

The trace file400can also include key frames, which are depicted as shaded horizontal lines (e.g., such as particularly identified key frames403a-403f). A key frame is a type of data packet that stores sufficient information to begin replay execution of an executable entity from the time of the key frame onward. For example, a key frame may store values for all relevant processor registers, information necessary to reproduce memory values from that point onward, etc. InFIG. 4, there is a key frame at the beginning of each trace data stream401(i.e., key frames403a-403c), and a key frame at sequencing numbers 1-7, 9, and 11 (e.g., key frame403dat sequencing number 2). Any number of key frames may be saved at any point in a data stream401, and need not occur at the same time across data streams. For example, in addition to the foregoing key frames,FIG. 4also depicts a key frame403eoccurring in data stream401abetween sequencing numbers 4 and 5, and a key frame403foccurring in data stream401cbetween sequencing numbers 7 and 12.

As mentioned above, key frames enable the replay component202to initiate replay of each trace data stream401at various points. For example, referring to data stream401a, the replay component202can use key frames to initiate execution at different parts in the stream, including at the start of the stream (i.e., using key frame403a), at sequencing numbers 1, 4, 5, and 9 (which, as depicted, each also correspond with a key frame), and at key frame403ebetween sequencing numbers 4 and 5. Each section of a particular trace data stream that is bounded by key frames is independent from other sections of that trace, and can also be replayed in parallel. For example, key frames depicted in data stream401a, define five such sections (i.e, a first section bounded by key frame403aand the key frame at sequencing number 1, a second section bounded by the key frame at sequencing number 1 and the key frame at sequencing number 4, a third section bounded by the key frame at sequencing number 4 and key frame403e, a fourth section bounded by key frame403eand the key frame at sequencing number 5, and a fifth section bounded by the key frame at sequencing number 5 and the key frame at sequencing number 9). Each of these sections is independent from the others, and can be replayed in parallel with those sections.

Thus, independently recorded streams and orderable events/sequencing numbers enable portions of different data streams401to be replayed in parallel. In addition, key frames within individual data streams enable different sections of the same data stream to be replayed in parallel.

Referring now toFIGS. 2-4, in order to create individual persistence data structures (e.g.,304a-304f) based on trace file400, the identification component201can identify individual trace sections401(e.g., sections between key frames and/or sequencing numbers), and identify one or more orderings among these sections (e.g., based on the sequencing numbers). The replay component201can then replay these trace sections, potentially in parallel, while the persistence component203stores encountered memory locations/values in a persistence data structure304corresponding to each trace section.

In addition, in order to return a memory value for an event of interest, the identification component201can identify an executable event of interest in the trace file400, including a memory address of interest that corresponds to that executable event (e.g., a memory address read from or written to by that event). The identification component201can then identify independent trace sections among the trace data streams401that would execute prior to that event, and which persistence data structures (e.g.,304a-304f) correspond to those trace sections. The identification component201also can identify one or more orderings among these trace sections based, for example, on the sequencing numbers. The search component204then searches through the identified persistence data structures304, in turn, using an ordering identified by the identification component201, until the memory address of interest is encountered. The presentation component205then returns a value of the memory address of interest from the persistence data structure.

Of course, the persistence data structures304need not exist prior to a request for a memory value. For example, after the identification component201identifies independent trace sections among the trace data streams401that would execute prior to that event, the identification component201may determine that one or more of the corresponding persistence data structures304does not yet exist. Thus, the replay component202can then replay the identified trace sections to create the persistence data structures304on-demand.

In order to provide a more concrete example,FIG. 5illustrates an example timing diagram500of replay of trace file400ofFIG. 4, with a specified event of interest502. In particular,FIG. 5illustrates a timeline showing replay of executable entity501aas recorded by data stream401a, replay of executable entity501bas recorded by data stream401b, and replay of executable entity501cas recorded by data stream401c. The timing diagram500also represents the occurrence of the orderable events ofFIG. 4, including sequencing numbers 1-12. InFIG. 5, key frames are denoted with a vertical line. Thus, sequencing numbers 1-7, 9 and 11 are depicted in connection with a key frame. For brevity, key frames occurring at a sequencing number are identified herein by the corresponding sequencing number. For example, the key frame at the beginning of data stream401ais referred to herein as key frame 1. The timing diagram500also represents four additional key frames502a-502dnot occurring along with a sequencing number, including key frames502aand502bat the beginning of data streams401band401c, and key frames502cand502doccurring in data streams401aand401c(i.e., corresponding to key frames403eand403finFIG. 4).

In this example, different trace sections are defined based on bounding key frames. For brevity, these sections are identified generally herein based on the two key frames bordering the sections, separated by a colon (:). Thus, for example, 1:4 refers the trace section that occurs between the key frame at sequencing number 1 and the key frame at sequencing number 4. Additionally, use of a square bracket (i.e., “[” or “]”) indicates the endpoint as being inclusive, and use of a parenthesis (i.e., “(” or “)”) indicates the endpoint as being exclusive. Thus, for example, [1:4) would denote section a section beginning with the instruction at sequencing number one, and ending with the instruction just prior to sequencing number 4.

As mentioned, the identification component201chooses one or more orderings among the trace sections. In some embodiments the chosen ordering defines a total ordering across all instructions in the trace file400. Such an ordering may be chosen to ensure that a debugger can present a consistent view of program state (e.g., memory and registers) at all points in the trace, and no matter how the replay component202actually arrived at that point in execution (e.g., whether it performed a forward replay or a backwards replay to arrive at a breakpoint). However, other embodiments may present one of multiple valid orderings each time a different point in the trace is reached. While this would result in a different view of program state being presented at different times, such an implementation may decrease implementation complexity and result in increased replay performance compared to use of an ordering that defines a total ordering across all instructions. Additionally, as explained in more detail below, the chosen ordering also provides an ordering with which the search component204searches persistence data structures304(though in reverse order).

Whatever the chosen ordering, valid orderings place the trace sections in an order that would ensure that sequencing events are presented in proper order (i.e., in their monotonically increasing order), but do not need to reproduce the exact order in which all instructions executed at trace time. For example, in reference toFIG. 5, a valid ordering needs to ensure that the instruction at sequencing event three is presented prior to the instruction at sequencing event four—but does not need to ensure that the instruction just after sequencing event three is presented prior to the instruction just after sequencing event four, since they are in different threads (and since, as discussed previously, threads are recorded independently). Thus, for example, a valid ordering would place section 3:7 prior to trace section 4:502c.

A valid ordering need not include sections from all traces (e.g., because execution of one thread may not be relevant to obtaining desired data at a given point of interest), and multiple valid orderings could be chosen. One valid ordering using only trace data streams401aand401cthat could be chosen to arrive at event of interest504is: [1:4), [502b:3], [4:502c), (3:7), [502c:5), and [5:9). Another valid ordering using all the trace data streams could be: [1:4), [502a:2), [502b:3), [2:6), [3:7), [4:502c), [502c:5), and [5:9). An example of an invalid ordering among trace sections is [1:4), [502b:3), [4:502c), [3:7), since this would present the event at sequencing number 4 as being visible, executed, and/or replayed prior to the event a sequencing number 3 (which would violate the trace memory model).

The replay component202need not actually perform the replay of the code sections according to this determined ordering. Instead, replay component202can execute the sections in any order, so long as the results obtained by the replay are presented according to the constraints of the determined ordering. Thus, the replay component202can queue the trace sections for replay in any order, and can execute them in any order at one or more processing units102a, so long as the results are presented in the chosen ordering.

FIG. 5also illustrates seven persistence data structures503a-503g(referred to generally as persistence data structures503), each of which corresponds to one of the trace sections. For example, persistence data structure503acorresponds to section 1:4, persistence data structure503bcorresponds to trace section502a:2, etc.

As described above, each persistence data structure503is created by the persistence component203while the replay component202replays the corresponding trace section. In some embodiments, the persistence component203writes into each persistence data structure503the memory addresses that are consumed by a processing unit102aas that processing unit replays executable events in the corresponding trace section, as well as the memory values consumed at those addresses. A memory address/value may be consumed due to a memory read or a write operation by an executable event. As mentioned above, in some embodiments, a persistence data structure is created by recording evictions from cache303, though it may be created in some other way.

In some embodiments, each persistence data structure503only records the most recently seen value at a memory address for a give trace section. Thus, for example, in trace section502a:2 the same memory address is consumed two times (as indicated by the ticks), and in trace section502b:3 that memory address is again consumed three times; however, there is only one entry for the memory address in each of persistence data structures503band503c(as indicated by the solid circles in persistence data structures503band503c). Those entries reflect the value seen the final time the address was consumed in that section (e.g., the farthest right memory address consumption in each section). Thus, in the case of subsequent encounters with the same memory address for a given trace section, the persistence component204overwrites a prior value associated with that address in the section's persistence data structure503. As will become clear later, recording only the latest value seen brings about efficiencies during search by the search component204.

Additionally, creation of a given persistence data structure503may be fully independent for that data structure, or may utilize information from another persistence data structure503. For example, when creating persistence data structure503f(based on section 2:6), it may be initially populated, at least in part, with values from persistence data structure503b(based on section503b:2), if it exists. Note that due to the independence of trace sections, and the use of parallel replay of trace sections across a plurality of processing units102a, it may be that section 2:6 is actually replayed prior to section503b:2, and that persistence data structure503bthus does not yet exist when creating persistence data structure503f.

FIG. 5also includes a point of interest504in section 5:9 that consumes a memory address, such as the memory address already referred to in connection with sections502a:2 and502b:3 and persistence data structures503band503c. Point of interest504may, for example, be a user-specified point of interest.

In some embodiments, when the value of a memory address seen by an event is requested, the events prior to that event are first consulted. For example, when attempting to return the value of the memory address consumed by event of interest504, the replay component202may first replay events505prior to that event (i.e., starting at key frame 5) in section 5:9 in order to determine if the same memory address was consumed by those events. If it was, then the replay component202can simply return that value. Alternatively, if a persistence data structure already exists for section 5:9, the search component search component204can locate the value in that persistence data structure.

Additionally or alternatively, if the persistence data structures503are created based on recording evictions from the cache303, the replay component may also consult the cache303to see if a cache line corresponding to the memory address. If it's in the cache303, then the replay component202can return the value from the cache303.

If, however, the memory address was not consumed by events prior to the event of interest in the same trace section, and/or if it is not in the cache303(in implementations in which the persistence data structures503are created based on cache evictions), the search component204searches persistence data structures503from prior trace sections, in reverse order based on the defined ordering, until a persistence data structure503recording the memory address is found. Thus, using the example ordering above of [1:4), [502a:2), [502b:3), [2:6), [3:7), [4:502c), and [502c:5), the search component204would initiate a search of persistence data structures503in the order of503g,503f,503e,503d,503c,503b, and503a. In the illustrated case, the search component204would actually search persistence data structures503g,503f,503e,503d, and503c, stopping at persistence data structure503cwhere it obtains the value. Note that because the persistence data structures503record only the most recently seen value, there is no need to continue searching once a match is found. Thus persistence data structures503band503aare not searched.

As mentioned above, persistence data structures503may be created prior to a request of a memory value, or may be created on-demand when a request is made. It will be appreciated that persistence data structures503may be persisted to durable storage (e.g., in persisted replay data110). As such, the persistence data structures503may be created not only in a current debugging session, but may have been created from an entirely separate prior debugging session. In addition, embodiments may also discard persistence data structures503in order to preserve memory and/or disk space. For example, embodiments may discard the least recently created persistence data structures503, the least recently accessed persistence data structures503, etc.

Notably, in some embodiments, some of the persistence data structures503may be combinable. For example, adjacent persistence data structures that are separated by a key frame that does not correspond to a sequencing number may, in some embodiments, be merged or combined into a single structure. Thus, for example, persistence data structures503dand503emaybe combinable.

In view of the foregoing,FIG. 6illustrates an example flow chart of a method600for preserving memory values during trace replay.FIG. 6is described in connection with the components and data described in connection withFIGS. 1-5. While method600is illustrated as a series of acts, the particular ordering of the acts in the method600is not limited to the ordering shown.

As illustrated, method600includes an act601of identifying a plurality of trace sections. Act601can comprise identifying, from among a plurality of trace data streams, a plurality of trace sections that each represents one or more events executed by an executable entity over a period of time. For example, the identification component201can identify a plurality of trace sections (e.g., sections 1:4,502a:2,502b:3, 2:6, 3:7, 4:502c,502c:5, and 5:9, as seen inFIG. 5) from among trace data streams401of trace file400, to be replayed by the replay component202. These trace sections may be selected based on routine replay of a trace file400, or may be selected based on a specific request (e.g., for event of interest504at a debugging application) to obtain a value of a memory address for a particular event of interest.

Method600also includes an act602of performing a parallel replay of the trace sections. Act602can comprise performing a parallel replay of two or more of the plurality of trace sections at the plurality of processing units, including concurrently replaying each trace of the two or more trace sections at a different processing unit of the plurality of processing units. For example, the replay component202can queue a plurality of trace sections (e.g., sections 1:4,502a:2,502b:3, 2:6, 3:7, 4:502c,502c:5, and 5:9) for replay by the processing units102a. The processing units102acan then replay each trace section independently, and in any order.

Method600also includes an act603of maintaining a persistence data structure corresponding to each trace section. Act603can comprise, while concurrently replaying each trace section at a different processing unit, maintaining a different persistence data structure corresponding to each trace section. For example, the persistence component203can maintain persistence data structures304/503, including a different persistence data structure for each trace section that is being replayed.

As depicted, act603also includes an act604of storing a most recent value stored at each memory address consumed by each trace section. Act604can comprise, for each trace section, storing, in the trace section's corresponding persistence data structure, a record of each memory address consumed by the processing unit while replaying the trace section, and a most recent memory value stored at each memory address during replay of the trace section. For example, the persistence component203can record, in each persistence data structure503, each memory address encountered during replay of the corresponding trace section along with values encountered. Also, each persistence data structure503includes only the most recently seen value at each address. Thus, as depicted inFIG. 5, trace sections502a:2 and502b:3 both encountered the same memory address multiple times, but their persistence data (503band503c) only each include a single entry for that address, storing the most recently seen value for that address. In some embodiments, the persistence component203maintains the persistence data structures503by recording the evictions from the cache303.

Although not depicted, the method600may also include defining an ordering among the plurality of trace sections based at least on orderable events across the plurality of trace data streams. For example, the identification component201can identify an ordering among sections 1:4,502a:2,502b:3, 2:6, 3:7, 4:502c,502c:5, and 5:9) based, at least in part, on the sequencing numbers. While these sections can be replayed individually and in any order by the processing units102a, the results of the replay are presented based on the defined ordering, in order to provide a valid view of execution that can be used for later analysis, such as by search component204.

Additionally,FIG. 7illustrates an example flow chart of a method700for returning a memory value during trace replay.FIG. 7is described in connection with the components and data described in connection withFIG. 1-5. While method700is illustrated as a series of acts, the particular ordering of the acts in the method700is not limited to the ordering shown.

As illustrated, method700includes an act701of identifying an event for which a memory value at a memory address is requested. Act701can comprise identifying, in a particular trace data stream, an event for which a memory value at a memory address associated with the event is requested. For example, the identification component201can identify an event of interest504in data steam401aof trace file400. The event of interest may, for example, be an event of interest specified in a debugging application.

Method700also includes an act702of identifying an ordering among trace sections across a plurality of trace data streams. Act702can comprise identifying a defined ordering among a plurality of trace sections across a plurality of trace data streams that include the particular trace data stream. For example, the identification component202can identify an ordering among trace sections 1:4,502a:2,502b:3, 2:6, 3:7, 4:502c,502c:5, and 5:9 ofFIG. 5based, at least in part the sequencing numbers.

Method700also includes an act703of identifying a plurality of persistence data structures, each associated with a different trace section. Act703can comprise identifying a plurality of persistence data structures that are each associated with a different trace section, and that occur prior to the location in the trace data stream based on the defined ordering. For example, the identification component202can identify persistence data structures503a-503e, corresponding to trace sections 1:4,502a:2,502b:3, 2:6, 3:7, 4:502c,502c:5, and 5:9.

Method700also includes an act704of identifying an ordering among the plurality of persistence data structures. Act704can comprise identifying an ordering among the plurality of persistence data structures based on the defined ordering. For example, the identification component202can identify an ordering of the persistence data structures503, based on a reverse ordering of the trace sections. Thus, for example, the identification component202can identify an ordering of the persistence data structures503as:503g,503f,503e,503d,503c,503b, and503a.

Method700also includes an act705of searching the persistence data structures, in turn, until the memory address is identified. Act705can comprise searching, in turn, and based on the identified ordering among the plurality of persistence data structures, one or more of the plurality persistence data structures until the memory address is identified in a particular persistence data structure. For example, the search component204can initiate a search for the requested memory address according to the ordering identified in act704. In this case, the search component204would identify the requested memory address in persistence data structure503c.

Method700also includes an act706of ceasing further searching and returning a value stored in a persistence data structure. Act706can comprise, when the memory address is identified in the particular persistence data structure ceasing further searching the plurality persistence data structures, and returning the value associated at the memory address, as stored in the particular persistence data structure. For example, upon identifying the requested memory address in persistence data structure503c, the search component204can cease the search, and then the presentation component205can return/display the value stored for the address in persistence data structure503c.

Although not depicted inFIG. 7, the method700may include one or more of (i) prior to searching the persistence data structures, replaying one or more instructions in the particular data stream that occurs between an orderable event and the event for which a memory value is requested to search for the memory address, or (ii) prior to searching the persistence data structures, searching a processor cache for the memory address.

The embodiments described herein preserve memory values during trace replay by maintaining plurality of persistence data structures during trace replay, which then provide an efficient mechanism returning a memory value, by progressively searching these persistence data structures only until the memory address of the requested memory value is encountered.