Patent Description:
When developing software applications, developers commonly spend a significant amount of time "debugging" application code to find runtime errors (e.g., undesired behaviors and software crashes) in the code. In doing so, developers may take several approaches to reproduce and locate 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 the code that causes a given undesired behavior or software crash can occupy a significant portion of application development time.

Many types of debugging software 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 memory and register values at various times during code execution, may enable developers to alter code execution paths, and/or may enable developers to set breakpoints that pause application execution and present program state at the time the breakpoint triggers.

An emerging form of debugging applications enable "time travel," "reverse," or "historic" debugging, in which execution of one or more of a program's threads are recorded/traced by tracing software and/or hardware into one or more trace files. Using some tracing techniques, these trace file(s) contain a "bit-accurate" trace of each traced thread's execution, which can be then be used to replay each traced thread's execution later for forward and backward analysis. Using bit-accurate traces, each traced thread's prior execution can be reproduced down to the granularity of its individual machine code instructions.

Some trace recording techniques record a bit-accurate trace based, in part, on recording processor data influxes (e.g., cache misses, uncached reads, etc.) during execution of each traced thread's machine code instructions by the processor. These recorded processor data influxes enable a time travel debugger to later reproduce any memory values that were read by these machine code instructions during replay of a traced thread. When recording based on processor data influxes, the resulting traces do not contain the entire state of memory at every moment in time; instead they contain information that can be used to incrementally modify such memory state just as the original program modified memory state.

Being able to search for byte patterns, such as strings, in these bit-accurate traces could be quite useful during debugging (e.g., as part of searching for exception records, as part of searching for error messages, etc.). However, because these bit-accurate traces lack the entire state of memory at every moment in time, these traces-themselves-lack all of the byte patterns that were read and written during execution of the traced thread(s). Thus, even though a thread may have read a given byte pattern from memory or written the given byte pattern to memory (e.g., as part of generating an exception, as part of displaying or logging an error message, etc.), this byte pattern may not actually appear in a trace data stream itself. As such, there are significant challenges in efficiently searching these bit-accurate traces for particular byte patterns.

Document <CIT> discloses performing a search over an indexed time-travel trace. A method includes receiving a search expression including one or more search criteria. The search expression is targeted at one or more trace data streams storing a trace of program execution. Based on the one or more search criteria, a plurality of families of code entity invocations are identified.

At least some embodiments described herein provide for indexing arbitrary length values at arbitrary alignments in bit-accurate traces that contain information sufficient to incrementally modify memory state (and that lack a full snapshot of memory at every point in time). In embodiments, such indexing produces one or more index data structures that associate different unique byte patterns (e.g., n-grams) with location(s) in the time-travel trace at which the byte pattern was seen in memory (e.g., read from and/or written to memory) during a recorded prior execution of a given thread. Leveraging these index data structure(s), a debugger can efficiently determine whether a given pattern of bytes was seen during the prior recorded prior execution. Then, if the pattern of bytes was seen during the prior recorded prior execution, the debugger can efficiently determine precisely when (e.g., in terms of execution time and memory location) the pattern of bytes was seen.

According to an embodiment of the invention, indexing a time-travel trace for values read or written by one or more threads over time comprises determining a format of n-grams for indexing in a time-travel trace that records a prior execution of one or more threads, and identifying a plurality of trace segments in the time-travel trace that are to be indexed based on the set of n-grams. The format of n-grams defines a gram-type and the gram size n. Each trace segment records the prior execution of the one or more threads at a different prior execution time. Each of the plurality of trace segments are replayed and, for each of the plurality of trace segments, a corresponding set of n-grams (according to the determined format of n-grams), are identified that exist in one or both of (i) input data corresponding to one or more processor data influxes that resulted from the replay of the trace segment, or (ii) output data corresponding one or more stores to a processor cache that resulted from the replay of the trace segment. Based on generating the corresponding set of n-grams for each of the plurality of trace segments, an index data structure is generated. The index data structure associates each identified n-gram with one or more trace locations in which the n-gram was found. The index data structure associates each of one or more n-grams with one or more prior execution times during which the one or more threads read or wrote the n-gram.

According to another embodiment of the invention, searching a time-travel trace that is indexed for values read or written by one or more threads over time comprises receiving a query comprising a plurality of bytes to be queried for in a time-travel trace that records a prior execution of one or more threads. The time-travel trace comprises a plurality of trace segments that each records the prior execution of the one or more threads at a different prior execution time. A set of a plurality of n-grams that exist in the plurality of bytes are identified. Then, using an index data structure (i.e., which associates one or more sets of unique n-grams with one or more trace locations in the time-travel trace at which each unique n-gram was found), at least one trace location at which the one or more threads read or wrote one or more values overlapping with one or more n-grams in the identified set of n-grams is identified. Based on identifying the at least one trace location, at least a portion of at least one of the plurality of trace segments is replayed, and (i) one or more prior execution times in the trace segment at which the one or more threads read or wrote the one or more values overlapping with the one or more n-grams in the set of n-grams, and (ii) one or more memory locations storing the one or more values are identified. Based on the identified one or more prior execution times and one or more memory locations, data responsive to the query is generated. This data identifies (i) at least one prior execution time at which one or more of the plurality of bytes were read or written by the one or more threads, and (ii) one or more memory locations storing the one or more of the plurality of bytes.

To the accomplishment of the foregoing, <FIG> illustrates an example computing environment <NUM> that facilitates indexing a time-travel trace for values read or written by one or more threads over time and/or searching a time-travel trace that is indexed for values read or written by one or more threads over time. As depicted, computing environment <NUM> may comprise or utilize a special-purpose or general-purpose computer system <NUM> that includes computer hardware, such as, for example, one or more processor(s) <NUM>, system memory <NUM>, and durable storage <NUM>, which are communicatively coupled using one or more communications bus(es) <NUM>.

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 system. 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 processors <NUM> to implement the disclosed functionality of the invention. Thus, for example, computer storage devices may include the depicted system memory <NUM> and/or the depicted durable storage <NUM>, which can each store computer-executable instructions and/or data structures.

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 system <NUM>.

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 a network interface module (e.g., a "NIC"), and then eventually transferred to the system memory <NUM> and/or to less volatile computer storage devices (e.g., durable storage <NUM>) at the computer system <NUM>. Thus, it should be understood that computer storage devices can be included in computer system components that also (or even primarily) utilize transmission media.

Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computer system configurations, including, personal computers, desktop computers, laptop computers, message processors, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile telephones, PDAs, tablets, pagers, routers, switches, and the like. As such, in a distributed system environment, a computer system may include a plurality of constituent computer systems.

As illustrated, the durable storage <NUM> can store computer-executable instructions and/or data structures representing application programs such as, for example, an indexer <NUM>, a debugger 104b, and an application 104c (e.g., which could be a user-mode application and/or code that is executed in kernel mode). In general, the indexer 104a is usable to index one or more trace(s) 104d that record a bit-accurate representation of a prior execution of subject code (e.g., such as code of application 104c) in a manner that enables the debugger 104b to efficiently search for arbitrary byte patterns that the subject code read from and/or wrote to memory during the recorded prior execution. Notably, and as will be explained later, the indexer 104a enables the debugger 104b to efficiently search for a given byte pattern whether or not all of the bytes in the given byte pattern actually existed in memory in their entirety at any single moment in time during the prior execution of the subject code. The indexer 104a and the debugger 104b might each be a standalone application, might be integrated into the same application (such as a debugging suite), or might be integrated into another software component-such as an operating system kernel, a hypervisor, a cloud fabric, etc. The traces 104d might be recorded at computer system <NUM>, or they might be recorded at some other computer system and then be imported to durable storage <NUM>.

Although the indexer 104a and the debugger 104b are both depicted in durable storage <NUM>, it is noted that the indexer 104a and the debugger 104b might not exist at the same computer system. For example, the indexer 104a might index the traces 104d at one computer system, while the debugger 104b might operate on those indexed traces 104d at another computer system. In embodiments, the functionality of the indexer 104a and the debugger 104b might be distributable. Thus, for example, the indexer 104a might distribute indexing functionality across a plurality of computer systems, and/or the debugger 104b might distribute debugging functionality (including searching for arbitrary byte patterns) across a plurality of computer systems.

As such, those skilled in the art will also appreciate that the invention may be practiced in cloud computing environments.

A cloud computing model can be composed of various characteristics, such as on-demand self-service, broad network access, resource pooling, rapid elasticity, measured service, and so forth. A cloud computing model may also come in the form of various service models such as, for example, Software as a Service ("SaaS"), Platform as a Service ("PaaS"), and Infrastructure as a Service ("IaaS"). The cloud computing model may also be deployed using different deployment models such as private cloud, community cloud, public cloud, hybrid cloud, and so forth.

Some embodiments, such as a cloud computing environment, may comprise a system that includes one or more hosts that are each capable of running one or more virtual machines. During operation, virtual machines emulate an operational computing system, supporting an operating system and perhaps one or more other applications as well. In some embodiments, each host includes a hypervisor that emulates virtual resources for the virtual machines using physical resources that are abstracted from view of the virtual machines. The hypervisor also provides proper isolation between the virtual machines. Thus, from the perspective of any given virtual machine, the hypervisor provides the illusion that the virtual machine is interfacing with a physical resource, even though the virtual machine only interfaces with the appearance (e.g., a virtual resource) of a physical resource. Examples of physical resources including processing capacity, memory, disk space, network bandwidth, media drives, and so forth.

<FIG> details some of the components of processor(s) <NUM> that can be used to implement various embodiments described herein. As shown, each processor <NUM> can include (among other things) one or more processing unit(s) <NUM> (e.g., processor cores) and one or more cache(s) <NUM>. After loading code to be executed into system memory <NUM> (e.g., as shown by indexer 103a, debugger 103b, application 103c in system memory <NUM>), each processing unit <NUM> loads and executes machine code instructions via the caches <NUM>. During execution of these instructions, the instructions can use internal processor registers (not shown) as temporary storage locations and can read and write to various locations in system memory <NUM> via the caches <NUM> (e.g., using a "data" portion of the caches <NUM>). If a processing unit <NUM> requires data (e.g., code or application runtime data) not already stored in the caches <NUM>, then the processing unit <NUM> can initiate a "cache miss," causing the needed data to be fetched from the system memory <NUM> and stored in the caches <NUM>-while potentially "evicting" some other data from the caches <NUM> back to system memory <NUM>.

Generally, the caches <NUM> comprises a plurality of "cache lines," each of which stores a chunk of memory from a backing store, such a system memory <NUM>. For example, <FIG> symbolically illustrates the caches <NUM> using a table 106a, in which each row (i.e., cache line) in the table 106a stores at least an address and a value. The address might refer to a location (e.g., a memory cell) in system memory <NUM>. The address might be a physical address (e.g., the actual physical location in the system memory <NUM>), or address might be a virtual address (e.g., an address that is mapped to the physical address to provide an abstraction). Virtual addresses could be used, for example, to facilitate memory isolation between different processes executing at the processors <NUM>.

In embodiments, the traces 104d are recorded based, at least in part, on utilizing a processor cache (e.g., hardware caches such as caches <NUM>, emulated caches, etc.) to record the data that was read by the machine code instructions of a subject application. These embodiments are built upon an observation that processors (e.g., such as processor <NUM>, or an emulated processor) form a semi- or quasi-closed system. For example, once portions of data for a given thread (i.e., code data and runtime application data) of the subject application (e.g., application 104c) are loaded into the processor's caches (e.g., caches <NUM>), the processor can execute this thread by itself-without any external input-as a semi- or quasi-closed system for bursts of time. In particular, a processing unit (e.g., processing units <NUM>) could execute one or more of the thread's machine code instructions from a code portion of the processor's caches, while using runtime data stored in a data portion of the processor's caches, and while using the processor's internal registers. When the processing unit needs some influx of information (e.g., because a machine code instruction is accessing (or will access) code or runtime data that is not already in the processor's caches or that is stored in uncacheable memory, because additional machine code instruction(s) are needed, etc.), the processing unit can trigger a cache miss to cause that information to be brought into the processor's caches from system memory or perform an uncached read. The processing unit can then continue executing one or more additional machine code instructions using the new information until new information is again needed (e.g., due to a read to data not already in the caches, due to a read from uncacheable memory, etc.). A bit-accurate representation of execution of a given thread can therefore be recorded based, in part, on recording data (e.g., relating to the thread's cache misses and uncached reads) that is sufficient to reproduce any data that was read by the thread's machine code instructions during their execution. This trace data can then be used to as input to the thread's machine code instructions in order to replay the original execution of the thread.

In embodiments, the traces 104d include a plurality of different trace data streams, each of which records execution of a different traced thread. To illustrate this concept, <FIG> illustrates an example <NUM> of a plurality of trace data streams <NUM> (such as trace data streams that could make up traces 104d). While example <NUM> shows two trace data streams 201a and 201b, it will be appreciated (as indicated by the ellipses <NUM>) that the traces 104d could include any number (i.e., one or more) of trace data streams <NUM>. While, in embodiments, each trace data stream <NUM> could be fully independent, other embodiments could insert markers (not shown), such as monotonically incrementing values, into the trace data streams <NUM> that can be used to order some events between two or more trace data streams (e.g., such as accesses to shared variables).

In embodiments, each trace data stream <NUM> could include a plurality of key frames <NUM> (e.g., key frames 203a-<NUM> through 203a-<NUM> in trace data stream 201a, and key frames 203b-<NUM> through 203b-<NUM> in trace data stream 201b). Each key frame <NUM> can contain data sufficient to enable replay of the trace data stream <NUM> to be commenced beginning at the key frame. Thus, for example, each key frame <NUM> could include then-current processor state such as register values. In embodiments, there might even be "heavy" key frames (e.g., key frame 203a-<NUM>) that include additional information, such as memory snapshot data. As a result of key frames <NUM>, each trace data stream <NUM> is divided into a plurality of independent trace segments <NUM> (e.g., trace segments 204a-<NUM> through 204a-<NUM> in trace data stream 201a, and trace segments 204b-<NUM> through 204b-<NUM> in trace data stream 201b). Key frames <NUM> could occur at any interval. For example, in trace data stream 201a they appear at irregular intervals (e.g., near function calls, near exceptions, near context switches, etc.) resulting in irregular trace segment <NUM> sizes, while in trace data stream 201b they appear at regular intervals (e.g., every "n" number of instructions) resulting in regular trace segment <NUM> sizes.

Within the context of computer system <NUM> of <FIG>, and trace data streams <NUM> of <FIG>, <FIG> illustrates an example <NUM> of an indexer <NUM> (e.g., corresponding to indexer 104a) that can be used to index bit-accurate traces 104d in a manner that enables efficient searches for arbitrary byte patterns that the subject code read from and/or wrote to memory during its prior execution. As depicted, the indexer <NUM> includes a variety of components (e.g., n-gram format determination <NUM>, segment identification <NUM>, segment replay <NUM>, n-gram identification <NUM>, index generation <NUM>, etc.) and data structures (e.g., index data structure <NUM>) that represent various functionality the indexer <NUM> might implement in accordance with various embodiments described herein. It will be appreciated that these components and data structures-including their identity and arrangement-are depicted merely as an aid in describing various embodiments described herein, and that these components/data structures are non-limiting to how software and/or hardware might implement various embodiments described herein.

In embodiments, the indexer <NUM> indexes the traces 104d based on "n-grams" of a defined size that were read from and/or written to memory by the subject code. As will be appreciated by one of skill in the art, n-gram is a contiguous sequence of "n" items (or grams) from a given sample. An n-gram of gram-size <NUM> is referred to as a "<NUM>-gram" or "unigram," an n-gram of gram-size <NUM> is a "<NUM>-gram" or "bigram," and n-gram of gram-size <NUM> is a <NUM>-gram or "trigram," and so on. The grams taken from a sample can be virtually anything-n-grams are commonly used to identify sequences of phonemes, syllables, letters, words, base pairs, etc. As a simple example, assuming that each gram is a different word, the phrase "to be or not to be" would include the trigtram sequences: "to be or," "be or not," "or not to," and "not to be.

In general, the indexer <NUM> indexes one or more trace data streams in the traces 104d based identifying sets of n-grams that appear in (i) any processor data influxes (e.g., cache misses and uncached reads) caused by the traced thread(s) that are being indexed (i.e., memory values read by the traced threads), and (ii) any data writes (e.g., to a processor cache) by these threads (i.e., memory values stored by the threads). In order to identify these sets of n-grams, the indexer <NUM> may need to replay the traces 104d (or at least subsets thereof) so that the traced code reproduces the data writes that occurred during its original execution. The indexer <NUM> then produces an index that maps each n-gram that was identified with the location(s) in the traces 104d (e.g., trace segments <NUM>, individual executable instructions, function call instances, etc.) whose execution caused a memory read or store that overlapped with the n-gram.

The n-gram format determination component <NUM> identifies one or more n-gram formats that are to be used to index the traces 104d. In embodiments, the n-gram format determination component <NUM> determines what type of grams to use for the n-grams, while in other embodiments, the n-gram format determination component <NUM> uses a hard-coded or user-selected gram type. In embodiments, this gram type is individual bytes (i.e., eight bits), however, the n-gram format determination component <NUM> could use any appropriate type of gram, such as sets of two bytes, sets of four bytes, etc..

The n-gram format determination component <NUM> also identifies a gram-size. While the gram-size could also be a hard-coded or user-configurable choice, in embodiments, it is a dynamic choice that is made by the n-gram format determination component <NUM> based on factors such as acceptable index size, a size of the traces 104d being indexed, available processing resources for carrying out the indexing, a word size of the processor that was used to generate the trace, etc. For example, when dealing with grams comprising bytes, the n-gram format determination component <NUM> might choose a gram-size on the order of two to eight (e.g., two, four, or eight bytes). The inventor has observed that using n-gram formats that are <NUM>-grams of bytes, <NUM>-grams of bytes, or <NUM>-grams of bytes generally strikes a favorable balance between acceptable index size and precision of the resulting index. The inventor has also observed that these n-gram formats align well with many processor word and/or cache line sizes. The examples herein use an n-gram format of <NUM>-grams of bytes. It is noted that the n-gram format determination component <NUM> could, in some implementations, identify multiple n-gram formats for indexing-such as both <NUM>-grams of bytes and <NUM>-grams of bytes.

The segment identification component <NUM> identifies one or more trace segments <NUM> from the traces 104d that are to be indexed based on the chosen n-gram format. This might include all trace segments <NUM> in a given trace data stream <NUM> or could be a subset of segments <NUM> in the trace data stream <NUM>. The choice of these trace segments <NUM> could be made based, for example, based on which execution time period(s) to be indexed (e.g., a subset of a prior recorded execution time or the entire recorded prior execution time), based on identified function(s) that are to be indexed, based on a subset of threads to be indexed, etc..

Once one or more n-gram formats are determined by the n-gram identification component <NUM>, and once one or more trace segments <NUM> to be indexed are identified by the segment identification component <NUM>, the segment replay component <NUM> and the n-gram identification component <NUM> can cooperate to identify which n-grams of the determined n-gram format appear in the memory values read and written by the traced code during each selected trace segment <NUM>. In embodiments, this is accomplished by the segment replay component <NUM> replaying execution of all, or part, of each trace segment <NUM>, while the n-gram identification component <NUM> identifies a set of one or more n-grams in the selected n-gram format(s) that appear in any lines of cache data imported into a processor cache during the replay (i.e., the cache misses recorded in the traces 104d), any uncached values that were read during the replay, and/or in data written to the processor cache during the replay. Notably, because the segment replay component <NUM> and the segment identification component <NUM> can operate on independently-replayable trace segments, it might be possible to distribute the work of replay and segment identification across a plurality of computer systems for parallel processing of the traces 104d.

By way of demonstration, <FIG> illustrates an example 400a of identification of n-grams in a series of bytes of memory at the same time. In particular, example 400a includes a first line <NUM> showing a series of bytes that might be read from or written to a cache line during replay of a given trace segment <NUM> (or even during replay of multiple trace segments <NUM>) by the segment replay component <NUM>. As shown, when interpreted as ASCII, this series of bytes might translate to a string that includes the popular pangram, "the quick brown fox jumps over the lazy dog. " As shown in a second line <NUM>, beginning at the first byte of this string (which could, for example, correspond to the beginning of a cache line), the n-gram identification component <NUM> might identify a first set of <NUM>-grams <NUM> of bytes (which, in this case, happen to each be unique), including <NUM>-gram 402a (i.e., "the "), <NUM>-gram 402b (i.e., "quic"), <NUM>-gram 402c (i.e., "k br"), and so on. As shown in a third line <NUM>, the n-gram identification component <NUM> might additionally identify a second set of <NUM>-grams <NUM> of bytes using a different byte alignment (here, beginning two bytes off from the first set set), including <NUM>-gram 403a (i.e., "e qu"), <NUM>-gram 403b (i.e., "ick "), <NUM>-gram 403c (i.e., "brow"), and so on. Notably, the n-gram identification component <NUM> might identify any number of sets of n-grams (i.e., one or more sets) using any chosen byte alignment for each set. Additionally, or alternatively, the n-gram identification component <NUM> might identify multiple sets of n-grams having a different gram-size for each set. As will become clear later, having multiple sets of n-grams with differing byte alignments and/or gram-sizes can increase the precision of the resulting index and help filter false positives during a later search.

Based on the n-gram identification component <NUM> having identified one or more sets of unique n-grams during replay of each trace segment <NUM>, the index generation component <NUM> can generate one or more index data structures <NUM> that aggregate these sets over all the trace segments <NUM> that were chosen for indexing. As shown, an index data structure <NUM> can associate a different unique n-gram with one or more locations in the traces 104d at which that n-gram was identified. Trace locations could be specified in a variety of ways, such as by individual machine code instruction, by trace segment <NUM>, by function instance, etc. If multiple sets of n-grams were identified during replay of each trace segment <NUM> (e.g., using sets of n-grams having different byte alignments and/or gram-sizes), the index generation component <NUM> might generate a different index data structure <NUM> for each set, or might tag a single index data structure <NUM> to indicate which set(s) a given n-gram belongs to. Once these index structure(s) are generated, the index generation component <NUM> might augment the traces 104d with the generated index data structures, such as by adding the generated index data structures as one or more additional trace data streams, by storing the generated index data structures as one or more separate trace files, etc. Since each index data structure <NUM> associates unique n-grams with different trace locations (e.g., instruction, trace segment <NUM>, function instance, etc.) each index data structure <NUM> inherently associates each n-gram with an execution time at which the n-gram was read from or written to memory (e.g., in the case of trace locations being instructions), or at least a time period over which each n-gram was read to or written from memory at least once (e.g., in the case of trace locations being trace segments <NUM>).

While, in <FIG>, the entire string "the quick brown fox jumps over the lazy dog" appeared in memory at the same time (i.e., within a single cache line), it may frequently be the case that a string of interest might not actually exist in memory, in its entirety, all at once. For example, <FIG> illustrates an example 400b of identification of n-grams in a series of bytes of memory at different times. In particular, presuming for purposes of example 400b that a cache line can store only <NUM> bytes, the first line <NUM> of example 400b shows that, rather than storing the full string of "the quick brown fox jumps over the lazy dog" at the same time, the cache line could instead store the sub-string "the quick brown fox " at a first time, the sub-string "jumps over the lazy, " at a second time, and the sub-string "dog" at a third time. The second line <NUM> of example 400b shows that the cache line could be indexed for one or more sets of n-grams at each of these different times (here, a single set of <NUM>-grams <NUM> of bytes). When these n-grams are indexed into the index data structure <NUM>, they enable searches for the full string "the quick brown fox jumps over the lazy dog" even though this full string did not actually exist in memory at any given time. This ability to search or query over time an also enable searches that have time dependencies, such as to locate where in a trace an occurrence of a first string (e.g., such as particular user input) was followed in execution time by one or more occurrences of a second string (e.g., such as a particular error message). Thus, for example, a query might be able to identify how often a given error message (e.g., the second string) appears following a given user input (e.g., the first string).

At times, a string might exist in memory at the same time, but it might span multiple adjoining cache lines. To illustrate this concept, <FIG> illustrates an example 400c of identification of n-grams in a series of bytes in memory that spans cache lines. In particular, presuming again for purposes of example 400c that a cache line can store only <NUM> bytes, the first line <NUM> of example 400c shows that, while the full string of "the quick brown fox jumps over the lazy dog" might be stored in memory at the same time, it could span multiple cache lines (e.g., 404a, 404b, etc.). The second and third lines <NUM> and <NUM> of example 400c shows that these cache lines 404a, 404b, etc. could be indexed for one or more sets of n-grams (here, sets of <NUM>-grams of bytes at different byte alignments). As shown in line <NUM>, the n-gram identification component <NUM> might refrain identifying n-grams that cross cache lines (e.g., the n-grams "x ju" and "y do"). When the indexer <NUM> does not index across cache lines, the debugger 104b might decrease the number of n-grams that need to be found in order to register a match on a given search string. For example, in the context of <FIG>, the debugger 104b might register a match on a search string of "the quick brown fox jumps over the lazy dog" when <NUM> out of a possible <NUM> n-grams in the search string are found.

It is noted that some applications might read and/or write a series of bytes to memory out of their proper order. This might happen, for example, if the traced application is performing encryption or compression. As an example, using a very simple encryption algorithm, the string "the quick brown fox jumps over the lazy dog" might be read or written in a jumbled order, such as "dog azy he ler ts ovjumpfox own k brquicthe " (i.e., which arranges groups of <NUM>-bytes of the string in reverse order). Notably, depending on the format(s) and alignment of the set(s) of n-grams identified, embodiments might enable searching even for strings that were read/written in jumbled orders (whether they existed in memory all at once, or over time).

In view of the foregoing, <FIG> illustrates a flowchart of an example method <NUM> of indexing a time-travel trace for values read or written by one or more threads over time. Method <NUM> will now be described in view of the architectures, components, and examples of <FIG>.

As shown in <FIG>, method <NUM> includes an act <NUM> of determining an n-gram format. Act <NUM> comprises determining a format of n-grams for indexing in a time-travel trace that records a prior execution of one or more threads. For example, the n-gram format determination component <NUM> might determine one or more n-gram formats, including a gram type (e.g., bytes) and a gram-size for each format, to be identified in traces 104d. In embodiments, example n-gram formats could be <NUM>-grams of bytes, <NUM>-grams of bytes, <NUM>-grams of bytes, and the like.

Method <NUM> also includes an act <NUM> of identifying a plurality of trace segments. Act <NUM> comprises identifying a plurality of trace segments in the time-travel trace that are to be indexed based on the determined format of n-grams, each trace segment recording the prior execution of the one or more threads at a different prior execution time. For example, the segment identification component <NUM> might identify a plurality of trace segments <NUM> in one or more trace data streams <NUM> of the traces 104d. In embodiments, each of these trace segments <NUM> could begin with a key frame <NUM> and record a prior execution of a plurality of machine code instructions.

Method <NUM> also includes an act <NUM> of replaying the trace segments. Act <NUM> comprises replaying each of the plurality of trace segments. For example, the segment replay component <NUM> might replay at least a portion of each of the trace segments <NUM> identified in act <NUM>, beginning with a key frame <NUM> at the beginning of each trace segment <NUM>.

Method <NUM> also includes an act <NUM> of, based on the replay, identifying a set of n-grams for each trace segment. Act <NUM> comprises, for each of the plurality of trace segments, identifying a corresponding set of n-grams, according to the format of n-grams, that exist in one or both of (i) input data corresponding to one or more processor data influxes that resulted from the replay of the trace segment, or (ii) output data corresponding one or more stores to a processor cache that resulted from the replay of the trace segment. For example, as the segment replay component <NUM> replays each identified trace section <NUM>, the n-gram identification component <NUM> might monitor any replayed processor data influxes (e.g., cache misses, uncached reads, etc.) and any replayed data writes (e.g., to a processor cache). The n-gram identification component <NUM> might then identify one or more sets of n-grams in the values of these replayed data influxes and the data writes. Referring to <FIG>, for example, the n-gram identification component <NUM> could identify different <NUM>-grams of bytes in the string "the quick brown fox jumps over the lazy dog," regardless of whether this string actually existed in its entirety in a single cache line at a single point in time, whether this string existed as subsets of the string in a single cache line at different times, or whether this string existed across multiple cache lines (at the same time or at different times).

In act <NUM>, the n-gram identification component <NUM> might identify n-grams of arbitrary sizes based on the chosen n-gram format(s). For example, the n-gram identification component <NUM> could identify n-grams sized based on a chosen gram type and/or a different gram-size. In embodiments, the n-gram format determination component <NUM> might have identified multiple n-gram formats in act <NUM>. Thus, in act <NUM>, identifying each corresponding set of n-grams could comprise identifying n-grams according to both the first format of n-grams and the second format of n-grams. In addition, in act <NUM>, the n-gram identification component <NUM> might identify n-grams at arbitrary byte alignments (e.g. starting at the beginning of each cache line, starting two bytes from the beginning of each cache line, etc.). Thus, when identifying each corresponding set of n-grams, act <NUM> might comprise identifying each n-gram in a single set of n-grams based on a single particular byte alignment, or identifying different sets of n-grams according to at least a first byte alignment and a second byte alignment.

In embodiments, act <NUM> might apply filtering to identify only a subset of n-grams that were read/written. For example, the n-gram identification component <NUM> might identify only n-grams that appeared in connection with execution of one or more identified functions. This could be useful, for example, to index only a subset of the traces 104d that relate to execution of these one or more identified functions. For instance, it might be desirable to index only n-grams relating to calling a logging function (e.g., by identifying only n-grams in data that was passed to the logging function as parameters). Accordingly, act <NUM> might also comprise determining whether each influx or each store corresponds to execution of one or more identified functions, and then only identifying n-grams in data corresponding to influxes or stores that correspond to execution of the one or more identified functions.

Method <NUM> also includes an act <NUM> of creating an index data structure. Act <NUM> comprises, based on generating the corresponding set of n-grams for each of the plurality of trace segments, generating an index data structure that associates each identified n-gram with one or more trace locations in which the n-gram was found, the index data structure therefore associating each of one or more n-grams with one or more prior execution times during which the one or more threads read or wrote the n-gram. For example, the index generation component <NUM> might generate one or more index data structures <NUM> (e.g., a different structure for each set of n-grams, or a single structure tagged with which set(s) each n-gram belongs to). These index data structures <NUM> can map unique n-grams with one or more locations in the traces 104d at which the n-gram was identified by the n-gram identification component <NUM>. These locations could be specified in several ways, such as by instruction, by trace segment <NUM>, by function instance, etc. If locations are specified by instruction (i.e., so that each location corresponds to execution of a single of machine code instruction), an index data structure could map each n-gram with any instruction recorded trace that read or wrote the n-gram. If locations are specified by trace segment <NUM> (i.e., so that each location corresponds to execution of a plurality of machine code instructions, beginning with a key frame), an index data structure could map each n-gram with each trace segment <NUM> in which the n-gram was seen at least once. Once one or more index data structures <NUM> are generated, they can be inserted by the indexer <NUM> into a time-travel trace (e.g., traces 104d) as one or more additional trace data streams, as one or more additional trace files, etc..

Accordingly, embodiments provide for indexing arbitrary length values at arbitrary alignments in a bit-accurate trace, even when that trace contains information to incrementally modify memory state, rather than a full snapshot of memory at every point in time. As described, this indexing produces one or more index data structures that associate different unique byte patterns (e.g., n-grams) with location(s) in the time-travel trace (e.g., particular instructions, trace segments, etc.) at which the byte pattern was seen (e.g., read and/or written) during a recorded prior execution of a given thread.

Once the traces 104d have been indexed in the foregoing manner, the debugger 104b can search for arbitrary query strings within these traces, based on identifying n-grams in the index data structures <NUM> that overlap with n-grams in the query strings. To illustrate this concept, <FIG> shows an example <NUM> of a search component <NUM> (e.g., a component of debugger 104b) that can be used to efficiently search indexed traces for arbitrary byte patterns that subject code read from and/or wrote to memory during a prior execution. As depicted, the search component <NUM> includes a variety of components (e.g., query input <NUM>, n-gram identification <NUM>, segment identification <NUM>, segment replay <NUM>, time and location identification <NUM>, query output <NUM>, etc.) that represent various functionality the search component <NUM> might implement in accordance with various embodiments described herein. It will be appreciated that these components and data structures-including their identity and arrangement-are depicted merely as an aid in describing various embodiments described herein, and that these components/data structures are non-limiting to how software and/or hardware might implement various embodiments described herein.

The query input component <NUM> can receive input (e.g., from a user or other software component) of a query that can include a sequence of a plurality of bytes. This sequence could include bytes that are contiguous or non-contiguous. For example, an example of a query for a contiguous sequence of bytes could be a query for anywhere memory contained (either all at once or incrementally) the phrase "the quick brown fox jumps over the lazy dog. " Another example of a query for a contiguous sequence of bytes could be a query for locations where memory contained the <NUM>-byte aligned value "0x_e034_c3f5_a849_dd37. " An example of a query for a non-contiguous sequence of bytes could be a query to find instances where memory contained a structure (e.g., _C_STRUCT) with "(field Alpha == 0x3 and field Beta == 0x1) OR (field Theta == EnumValueFoo and field Omega != 0x7F)". Another example of a query for a non-contiguous sequence of bytes could be a query to find instances of a byte sequence that can include gaps (*), such as 0x77 0x84 * 0x3f * 0x99.

The n-gram identification component <NUM> can generate one or more sets of n-grams from the byte sequence received by the query input component <NUM>. For example, if the query input component <NUM> were to have received the query "the quick brown fox jumps over the lazy dog," the n-gram identification component <NUM> might identify the <NUM>-grams of bytes shown in line <NUM> of <FIG> (i.e., "the ," "quic," "k br," and so on) using a first byte alignment and/or line <NUM> of <FIG> (i.e., "e qu," "ick ," "brow," and so on) using a second byte alignment.

The segment identification component <NUM> can identify candidate segment(s) in the traces 104d that were found by the indexer <NUM> to contain at least a subset of the n-grams that were identified by the n-gram identification component <NUM>. For example, the segment identification component <NUM> can consult one or more index data structures <NUM> (e.g., as part of the traces 104d) that were generated by the indexer <NUM>, and look up each of the n-grams identified from the query string. Based on consulting these index data structure(s) <NUM>, the segment identification component <NUM> can identify one or more locations in the traces 104d where at least a subset of these identified n-grams was found by the indexer <NUM>. As discussed in connection with the indexer <NUM>, these locations could be individual instructions, one or more trace segments <NUM>, function instances, etc. If needed (e.g., if these locations identify individual instructions), the segment identification component <NUM> might map those locations to trace segments <NUM> (e.g., by identifying a key frame occurring before each identified instruction). The segment identification component <NUM> can then select one or more of these trace segments <NUM> for replay. Notably, the segment identification component <NUM> might only find less than all of the n-grams that were identified from the query input in the trace segments <NUM> that are selected for replay. For example, if the indexer <NUM> did not index n-grams across cache line boundaries (e.g., as discussed in connection with <FIG>), it could be possible that some of the identified n-grams (e.g., "x ju" and "y do") might not be found in the index data structures <NUM>, even though they did, in fact, exist in memory during the traced execution. By permitting the segment identification component <NUM> to identify trace segments for replay that contain only a subset of the n-grams that were identified from the query input, the search component <NUM> can still query against data that crossed cache lines.

In embodiments, the segment identification component <NUM> could select only those trace segments <NUM> that were found to contain a minimum threshold number of the n-grams identified by the n-gram identification component <NUM>. For example, if the segment identification component <NUM> were to select all trace segments <NUM> that contain the n-gram "the " then the segment identification component <NUM> might turn up a lot of false positives. As such, the segment identification component <NUM> might select only a trace segment <NUM> (or group of adj acent trace segments <NUM>) that contains a certain percentage of the identified n-grams, a minimum number of the identified n-grams, etc. For example, if each trace segment <NUM> traces execution of a million instructions, the segment identification component <NUM> might look for a minimum threshold number of n-grams in a single trace segment <NUM>. Alternatively, if each trace segment <NUM> traces execution of only half a million instructions, the segment identification component <NUM> might look for that minimum threshold number of n-grams in groups of two adjacent trace segments <NUM>.

The segment replay component <NUM> can replay at least a portion of each of the trace segments <NUM> selected by the segment identification component <NUM> while the time and location identification component <NUM> searches for the prior execution time(s) and memory location(s) at which those n-grams appear (as part of processor data influxes and cache reads) during the replay. When multiple n-grams are found, the time and location identification component <NUM> can determine whether or not there was a "hit" on the original query, such as by determining whether different n-grams appear at "adjacent" or "nearby" memory locations. N-grams could be "adjacent" or "nearby" in terms of memory address (e.g., addresses within the same cache line, addresses within adjoining cache lines, etc.) and/or execution time (e.g., the values stored within a given cache line at different execution times). When a threshold number of the identified n-grams are found with enough "adjacency" or "nearness," the time and location identification component <NUM> can determine that there was a hit on the query, and note the execution time(s) and memory location(s) of the hit.

Notably, the identified n-grams may not necessarily appear in memory during repay in the same order as they did in the original query (e.g., due to encryption/compression, and the like). Also, because the segment replay component <NUM> and the time and location identification component <NUM> can operate on independently-replayable trace segments, it might be possible to also distribute the work of replay and time/location identification across a plurality of computer systems for parallel processing of the traces 104d.

In embodiments, the time and location identification component <NUM> might search for hits on the original query using n-grams aligned at a first byte alignment (e.g., the <NUM>-grams of bytes shown in line <NUM> of <FIG>). If there are no hits (or a low number of hits) using these n-grams, the time and location identification component <NUM> might then search for hits using n-grams aligned at a second byte alignment (e.g., the <NUM>-grams of bytes shown in line <NUM> of <FIG>). This could continue for even further byte alignments, as desired. Notably, the n-gram identification component <NUM> can identify n-grams at any byte alignment-and the time and location identification component <NUM> can search for those n-grams-regardless of whether or not those alignments were actually indexed. For example, the time and location identification component <NUM> could search for the <NUM>-byte aligned n-grams "he q," " qui," "uick," "ck b," " bro," and "rown," and so on, even if those n-grams were not indexed (in addition, or as an alternative to, searching for the n-grams in lines <NUM> and <NUM>).

In embodiments, the time and location identification component <NUM> might only find a hit on the original query if there are overlapping n-grams from two or more different byte alignments. For example, referring <FIG>, the time and location identification component <NUM> might find a hit only if it finds at least two (or more) n-grams from set of n-grams in line <NUM> (e.g., n-grams 402a and 402b, emphasized with heavy lines), as well as at least one (or more) n-gram from the set of n-grams in line <NUM> that overlaps with these two n-grams (e.g., n-gram 403a, also emphasized with heavy lines).

If the time and location identification component <NUM> identifies any hits on the original query, the query output component <NUM> can produce a query result that that identifies any prior execution time(s) at which one or more of the bytes from the query were read or written by the one or more threads, as well as one or more memory locations storing those bytes. This query result could be presented to a user or could be passed to some other software component.

Notably, the search component <NUM> could apply post-processing to potential matches prior to presenting them with the query output component <NUM>. For example, a query for "the quick brown" might result in the time and location identification component <NUM> searching for n-grams 402a-402d and n-grams 403a-403c, while requiring at least six matches. However, these n-grams could also match the string "the e ququicick k brbrowown " in addition to "the quick brown. " Post-processing could readily identify the correct result.

In view of the foregoing, <FIG> illustrates a flowchart of an example method <NUM> of searching a time-travel trace that is indexed for values read or written by one or more threads over time. Method <NUM> will now be described in view of the architectures, components, and examples of <FIG>.

As shown in <FIG>, method <NUM> includes an act <NUM> of receiving a query comprising a plurality of bytes. Act <NUM> comprises receiving a query comprising a plurality of bytes to be queried for in a time-travel trace that records a prior execution of one or more threads, the time-travel trace comprising a plurality of trace segments that each records the prior execution of the one or more threads at a different prior execution time. For example, the query input component <NUM> might receive a query comprising a series of a plurality of bytes. As discussed, this query could include a contiguous sequence of bytes (e.g., such as where memory contained the string "the quick brown fox jumps over the lazy dog"), or a non-contiguous sequence of bytes (e.g., such as where memory contained a structure (e.g., _C_STRUCT) with "(field Alpha == 0x3 and field Beta == 0x1) OR (field Theta == EnumValueFoo and field Omega != 0x7F)").

Method <NUM> also includes an act <NUM> of identifying n-grams in the query. Act <NUM> comprises identifying a set of a plurality of n-grams that exist in the plurality of bytes. For example, the n-gram identification component <NUM> might identify n-grams in the plurality of bytes received in act <NUM>. This might include, for example, identifying a first set of n-grams aligned to a first byte alignment, identifying a second set of n-grams aligned to a second byte alignment, etc..

Method <NUM> also includes an act <NUM> of identifying trace location(s) at which unique n-grams overlapping with the identified n-grams were seen. Act <NUM> comprises, using an index data structure, which associates one or more sets of unique n-grams with one or more trace locations in the time-travel trace at which each unique n-gram was found, to identify at least one trace location at which the one or more threads read or wrote one or more values overlapping with one or more n-grams in the identified set of n-grams. For example, the segment identification component <NUM> might compare n-grams listed in an index data structure <NUM> generated by the indexer <NUM> with the set of n-grams that were identified in act <NUM>. For each overlapping n-gram, the segment identification component <NUM> might identify one or more corresponding trace location(s) at which the n-gram was seen by the indexer <NUM>. As discussed, a trace location could be a machine code instruction executed during the at least one of the plurality of trace segments <NUM>, at least one of the plurality of trace segments <NUM>, an instance of a function call, etc. If a given trace location is a machine code instruction, the segment identification component <NUM> might identify a corresponding trace segment <NUM>, such as by identifying a key frame <NUM> that is prior to the machine code instruction in the traces 104d.

As discussed, the segment identification component <NUM> might choose one or more trace segments <NUM> for further analysis only if those segment(s) contain a minimum threshold number of the n-grams that were identified in act <NUM> (e.g., in terms of a percentage of n-grams from the original query, a minimum number of n-grams from the original query, etc.). Thus, act <NUM> might comprise identifying at least one trace segment during which the one or more threads read or wrote one or more values overlapping with a minimum threshold number of a plurality of n-grams in the identified set of n-grams.

Method <NUM> also includes an act <NUM> of replaying trace segment(s) corresponding to the trace location(s). Act <NUM> comprises, based on identifying the at least one trace location, replaying at least a portion of at least one of the plurality of trace segments. For example, the segment replay component <NUM> might replay at least a portion of any trace segment <NUM> chosen by the segment identification component <NUM> in act <NUM>, beginning with a key frame <NUM> at the beginning of the trace segment <NUM>.

Method <NUM> also includes an act <NUM> of, based on the replay, identifying prior execution time(s) and memory location(s) at which the identified n-grams were seen. Act <NUM> comprises identifying (i) one or more prior execution times in the trace segment at which the one or more threads read or wrote the one or more values overlapping with the one or more n-grams in the set of n-grams, and (ii) one or more memory locations storing the one or more values. For example, based on replay of the chosen trace segment(s), the time and location identification component <NUM> might observe values of processor data influxes and stores to a cache and compare them to one or more of the n-grams identified in act <NUM>. When there are enough n-grams that are sufficiently "adjacent' or "near" each other (in terms of memory addresses and/or execution time) the time and location identification component <NUM> could register a hit or match on the original query string. It could then note the prior execution time(s) and the memory location(s) of the matching n-grams, and/or of the hit generally.

In embodiments, registering a hit based on execution time might include, for example, the time and location identification component <NUM> identifying a first execution time at which the one or more threads read or wrote a first value overlapping with a first n-grams in the set of n-grams to a memory location, and a second execution time at which the one or more threads read or wrote a second value overlapping with a second n-grams in the set of n-grams to the same memory location. Registering a hit based on memory addresses might include, for example, the time and location identification component <NUM> identifying a first execution time at which the one or more threads read or wrote a first value overlapping with a first n-gram in the set of n-grams to a first cache line, and a second execution time at which the one or more threads read or wrote a second value overlapping with a second n-gram in the set of n-grams to a second cache line adjoining the first cache line.

As discussed, the time and location identification component <NUM> might limit possible matches by requiring that two (or more) n-grams that use a first byte alignment (e.g., n-grams 402a and 402b in <FIG>) overlap with one (or more) n-grams that use a second byte alignment (e.g., n-gram 403a in <FIG>). Thus, in some embodiments, act <NUM> could include identifying an execution time and memory location at which the one or more threads read or wrote one or more values overlapping with at least two n-grams aligned to the first byte alignment, as well as at least one n-gram aligned to the second byte alignment.

Method <NUM> also includes an act <NUM> of generating a query response that identifies prior execution time(s) and memory location(s) at which the identified n-grams were seen. Act <NUM> comprises, based on the identified one or more prior execution times and one or more memory locations, generating data responsive to the query that identifies (i) at least one prior execution time at which one or more of the plurality of bytes were read or written by the one or more threads, and (ii) one or more memory locations storing the one or more of the plurality of bytes. For example, the query output component <NUM> might generate a query response that includes the hits identified by the time and location identification component <NUM>. This query response could identify one or more instances of when (e.g., in terms of an execution time point) and where (e.g., in terms of a memory location) the plurality of bytes from the original query were found.

As was mentioned, embodiments might register a hit on a query string even if not all of the n-grams in the query string were found. This might be useful, for example, in cases when n-grams were not indexed across cache lines. Thus, in method <NUM>, the method might generate the data responsive to the query based on act <NUM> having identified at least one prior execution time at which the one or more threads read or wrote one or more values overlapping with at least a threshold number of n-grams in the set of n-grams, in which the threshold number of n-grams is less than all of the n-grams in the set of n-grams (i.e., a subset of those n-grams).

Accordingly, embodiments can leverage traces that are augmented with index data structure(s) generated by the indexer <NUM> to enable a debugger 104b to efficiently determine whether a given pattern of bytes was seen during the recorded prior execution. Then, if the pattern of bytes was seen during the recorded prior execution, the debugger 104b can efficiently determine precisely when (e.g., in terms of execution time and memory location) the pattern of bytes was seen and present this information to a user or other debugger component.

Claim 1:
A method, implemented at a computer system that includes one or more processors, for indexing a time-travel trace for values read or written by one or more threads over time, the method comprising:
determining (<NUM>) a format of n-grams for indexing in a time-travel trace that records a prior execution of one or more threads, the format defining a gram-type and the gram size n, wherein an n-gram is a contiguous sequence of n items and the gram-type represents the number of bytes in an item;
identifying (<NUM>) a plurality of trace segments in the time-travel trace that are to be indexed based on the determined format of n-grams, each trace segment recording the prior execution of the one or more threads at a different prior execution time;
replaying (<NUM>) each of the plurality of trace segments and, for each of the plurality of trace segments, identifying (<NUM>) a corresponding set of n-grams, according to the format of n-grams, that exist in one or both of (i) input data corresponding to one or more processor data influxes that resulted from the replay of the trace segment, or (ii) output data corresponding one or more stores to a processor cache that resulted from the replay of the trace segment; and
based on generating the corresponding set of n-grams for each of the plurality of trace segments, generating (<NUM>) an index data structure (<NUM>) that associates each identified n-gram with one or more trace locations in which the n-gram was found, the index data structure therefore associating each of one or more n-grams with one or more prior execution times during which the one or more threads read or wrote the n-gram.