In QEMU, how am I supposed to find the next TranslationBlock in a TB linked-list

Issue

I am trying to understand which guest instructions were executed after calling the function cpu_loop_exec_tb().

More specifically, I am trying to understand the relation between jmp_list_head, jmp_list_next and jmp_dest. According to the documentation of these fields in the code, the LSB of the pointer of jmp_list_next[0] or jmp_list_next[1] should be set which would indicate which branch was executed. But that is not always the case.

I am also puzzled to know which of jmp_dest or jmp_list_next should be used in order to get the next TranslationBlock pointer value (both contains valid pointers to instantiated TB). Sometimes, both jmp_dest and jmp_list_next have values while other times jmp_list_next are NULL but there are two jmp_dest.

For example:

cpu_loop_exec_tb()
last_tb    address: 
tb_exit:   0

EXEC:----------------
IN: 
0x00007de4:  88 f8                    movb     %bh, %al
0x00007de6:  88 fc                    movb     %bh, %ah
0x00007de8:  e8 e1 ff                 callw    0x7dcc

level:     0
tb         address: 0x00000253aca11cc0, LSB=0
tb.pc      address: 0x0000000000007de4, LSB=0
tb.cflags: 0xff020000.
jmp_target_arg: 0x0000000000000094, 0x0000000000000000.
incoming jumps:
tb->jmp_list_head: 
outgoing jumps:
tb->jmp_list_next[0]: 0x00000253aca11300, LSB=0
tb->jmp_list_next[1]: 
tb->jmp_list_next[0]->pc: 0x0000000000007dd6, LSB=0
tb->jmp_list_next[1]->pc: 
tb->jmp_dest[0]: 0x00000253aca11740, LSB=0
tb->jmp_dest[1]: 
tb->jmp_dest[0]->pc: 0x0000000000007dcc, LSB=0
tb->jmp_dest[1]->pc: 
STATUS: Following child TB 0x00000253aca11740: only jmp_dest[0] available.
Following child TB: : 0x00000253aca11740, LSB=0

EXEC:----------------
IN: 
0x00007dcc:  72 02                    jb       0x7dd0

level:     1
tb         address: 0x00000253aca11740, LSB=0
tb.pc      address: 0x0000000000007dcc, LSB=0
tb.cflags: 0xff020000.
jmp_target_arg: 0x0000000000000048, 0x0000000000000060.
incoming jumps:
tb->jmp_list_head: 0x00000253aca12300, LSB=0
outgoing jumps:
tb->jmp_list_next[0]: 
tb->jmp_list_next[1]: 
tb->jmp_list_next[0]->pc: 
tb->jmp_list_next[1]->pc: 
tb->jmp_dest[0]: 0x00000253aca118c0, LSB=0
tb->jmp_dest[1]: 0x00000253aca11e80, LSB=0
tb->jmp_dest[0]->pc: 0x0000000000007dce, LSB=0
tb->jmp_dest[1]->pc: 0x0000000000007dd0, LSB=0
tb->jmp_dest[0]->jmp_list_head: 0x00000253aca18c00, LSB=0
tb->jmp_dest[1]->jmp_list_head: 0x00000253aca13740, LSB=0
WARNING: Don't know which jmp_dest[] to choose from.


cpu_loop_exec_tb()
last_tb    address: 
tb_exit:   0

EXEC:----------------
IN: 
0x00007de4:  88 f8                    movb     %bh, %al
0x00007de6:  88 fc                    movb     %bh, %ah
0x00007de8:  e8 e1 ff                 callw    0x7dcc

In the log above, the returned TB from tb_find() is 0x00000253aca11cc0. The next TB in the linked list is obvious since jmp_list_next[0] program counter is not 0x7dcc and jmp_dest[0] program counter is 0x7dcc.

When looking at TB address 0x00000253aca11740, I do not understand how to select which TB is next since both jmp_dest are set.

Looking at other places in the code which I do not fully understand, I was expecting to evaluate the two jmp_dest, look at their jmp_list_head and see which of the two has the LSB set to 1. In the log above, both tb->jmp_dest[0]->jmp_list_head and tb->jmp_dest[1]->jmp_list_head have their LSB not set which seems to indicate this TB is a leaf while it is clearly not. To be clear, I sometimes see instances where either tb->jmp_dest[0]->jmp_list_head or tb->jmp_dest[1]->jmp_list_head have their LSB set to 1.

I know there are missing TB in the list that I was not able to print since the next executed PC is 0x7de4 (its not 0x7dd0 or 0x7dce).

The guest source code I am executing is this x86 Space Invaders game stored in the MBR.

Note: This is my first time posting on StackOverflow.

Note: I also read this question but it does not seem to solve my problem.

Solution

The TB linking is kind of complicated. Mostly you should be able to just ignore it. In particular, for most easily readable logs you should use '-d nochain' which will disable TB linking entirely. If you don't use 'nochain' then you can to some extent figure out executed TBs from the 'exec' logging by looking at when it says it is "Linking TBs" but this is a lot more painful.

Note also that TB chaining like this is not the only reason why cpu_loop_exec_tb() might execute more than one TB -- as well as this "goto_tb" mechanism which statically chains TBs together, there is also the "goto_ptr" mechanism, which does a dynamic "look up a pointer to the next TB if possible" chaining.

You should read the QEMU developer docs on TCG block chaining if you haven't already.

To answer your "which jmp_dest gets used?" question, this depends on what has happened inside the TB. TCG TBs can have up to 2 exits; the classic use for the 2 exit case is for a conditional branch. The generated code looks like "test the condition; if condition fails, take exit 0; if condition passes, take exit 1". (There's no requirement for 0 and 1 to be used in that order, incidentally.) You can't answer "which TB exit do we take?" just by looking at the TB data structure, because the answer is runtime dependent, and can be different each time the TB is executed. You can see this in your example log output: for TB 0x00000253aca11740, jmp_dest[0] points at a TB for guest PC 0x7dce, which is the "condition fails, execution falls through" case, and jmp_dest[1] points at a TB for guest PC 0x7dd0, which is the "condition passes, take the branch" case.

You have a misunderstanding also about the meaning of the LSB in the jmp_list_head value. The LSB is used as part of following the linked list of TBs which jump into this one: it tells us whether the next element in the list is to be found in jmp_list_next[0] or jmp_list_next[1]. You can walk the linked list of incoming jumps with something like this:

uintptr_t ptr_and_n = this_tb->jmp_list_head;
for (;;) {
    int n = ptr_and_n & 1;
    TranslationBlock *tb = (TranslationBlock *)(ptr_and_n & ~1);
    if (!tb) {
        break; /* end of linked list */
    }
    printf("next TB in incoming list: %p (it gets to us via its exit %d)\n",
           tb, n);
    ptr_and_n = tb->jmp_list_next[n];
}

(In QEMU this is what the TB_FOR_EACH_JMP macro does; I've written out a longhand equivalent here as hopefully a bit easier to understand.)

Finally, be aware that these links between TBs can be created and broken dynamically -- they are an optimization, and if there is no pre-created link from one TB to the next, QEMU will drop back to the main loop to find the next TB, hopefully adding the link if possible. Sometimes existing links are broken (eg if the TB being linked to is invalidated). When emulating an SMP guest some of this may be happening in parallel while your thread is walking the data structures, which is why there is a jmp_lock and why some changes to the fields must be made atomically.

Answered By - Peter Maydell