What does "execution trace" mean in Java Memory Model

Question

The part of the language specification dedicated to the Java Memory Model (JMM) (link) mentions "execution trace" a lot.

For example right from the start:

A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program. The Java programming language memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.

But I cannot find there any description/definition of this term.

So, what is "execution trace" exactly according to the JMM, and what exactly does it consist of?
References to specific places in the language specification text are most welcome.

Answer 1

You're right; it's not very clear. They also refer to it as "program trace", and simply "trace" on its own.

The following is a quote:

Consider, for example, the example program traces shown in Table 17.4-A.

Table 17.4-A.

Thread 1	Thread 2
B = 1;	A = 2;
r2 = A;	r1 = B;

So, it's simply an ordered list of statements, per thread, representing one possible permutation of how the statements may be executed (since statement may be reordered). A trace may be valid or invalid within the JMM; they are used to exemplify what is legal and what is not.

Answer 2

This is not a full-fledged answer, but I think this is worth mentioning.

Even if we don't know what an "execution trace" is in details, we can deduce which information it should provide.

Let's read the first paragraph of 17.4. Memory Model:

A memory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program. The Java programming language memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.

This means that "a program" (i.e. source code) and "an execution trace" should provide all the information required to determine whether the program execution is legal.
The information is described in 17.4.6. Executions.
I'm not going to copy-paste it here because it's too long.
I'll try to explain it in simple words instead:

• a program consists of statements, each statement consists of (possibly nested) expressions evaluated in some order
• an execution of a thread can be represented as a sequence of actions: one action per every simple expression
• an execution of a program is several threads executing in parallel
• an execution trace should provide information about actions performed during the program execution, i.e. it should provide provide the following information:

  • all executed actions: a sequence of actions per every thread

    Note: the JMM only cares about so called inter-thread actions (17.4.2. Actions):

    An inter-thread action is an action performed by one thread that can be detected or directly influenced by another thread

    Inter-thread action kinds:

    • read/write
    • volatile read/write
    • lock/unlock
    • various special and synthetic actions (e.g. thread start/stop, etc.)

  • for every action it should store:

    • thread id
    • action kind
    • what expression in the source code it corresponds to
    • for write and volatile write: the written value
    • for read and volatile read: the write action, which provided the value
    • for lock/unlock: the monitor being locked/unlocked
    • various relations with other actions (e.g. position in a so-called synchronization order for synchronization actions)