Indexing and searching a time-travel trace for arbitrary length/arbitrary alignment values

A method, implemented at a computer system that includes one or more processors, for searching a time-travel trace that is indexed for values read or written by one or more threads over time, the method comprising:

• 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;
• identifying a set of a plurality of n-grams that exist in the plurality of bytes;
• 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;
• based on identifying the at least one trace location, replaying at least a portion of at least one of the plurality of trace segments, and 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;
• and
• 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.

A computer system, comprising:

• one or more processors;
• and
• one or more computer-readable media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to perform at least the following:
• determine a format of n-grams for indexing in a time-travel trace that records a prior execution of one or more threads;
• identify 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;
• replay each of the plurality of trace segments and, for each of the plurality of trace segments, identify 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, generate 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.