[Qemu-devel] TB chaining

[Qemu-devel] TB chaining

[Xin Tong]

[-- Attachment #1: Type: text/plain, Size: 97 bytes --]

I am new to QEMU, can anyone please tell me where the TB chaining code is in
QEMU ?

Thanks

Xin

[-- Attachment #2: Type: text/html, Size: 114 bytes --]

Re: [Qemu-devel] TB chaining

[Lei Li]

On 09/22/2011 07:05 AM, Xin Tong wrote:

> I am new to QEMU, can anyone please tell me where the TB chaining code is in QEMU ?
Actually, TB chaining was implemented via TB list. You might want to look at Exec.c

In struct TranslationBlock, the following data are used to directly call another TB from
the code of this one.

     uint16_t tb_next_offset[2]; /* offset of original jump target */
#ifdef USE_DIRECT_JUMP
     uint16_t tb_jmp_offset[2]; /* offset of jump instruction */
#else
     unsigned long tb_next[2]; /* address of jump generated code */
#endif
     /* list of TBs jumping to this one. This is a circular list using
        the two least significant bits of the pointers to tell what is
        the next pointer: 0 = jmp_next[0], 1 = jmp_next[1], 2 =
        jmp_first */
     struct TranslationBlock *jmp_next[2];
     struct TranslationBlock *jmp_first; are used to directly call another TB from
        the code of this one

> Thanks
> Xin

-- 
Lei

Re: [Qemu-devel] TB chaining

[陳韋任]

>      /* list of TBs jumping to this one. This is a circular list using
>         the two least significant bits of the pointers to tell what is
>         the next pointer: 0 = jmp_next[0], 1 = jmp_next[1], 2 =
>         jmp_first */
>      struct TranslationBlock *jmp_next[2];
>      struct TranslationBlock *jmp_first;

  After tracing the code, I found the comment might be wrong.
For example, if we link tb1 to tb2, i.e., tb1 -> tb2. Then
"tb1->jmp_next[n] = tb2" and "tb2->jmp_first = tb1" (roughly
speaking). I'm not sure if I misunderstand the comment "list
of TBs jumping to this one", or it is just wrong. 

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[陳韋任]

> I am new to QEMU, can anyone please tell me where the TB chaining code is in
> QEMU ?

  struct TranslationBlock has fields used to to block chaining. You also
need to look into it.

cpu_exec (cpu-exec.c)

  It's the main execution loop where the interrupt/exception is handled
, and translared TB is found then executed.

  /* prepare setjmp context for exception handling */
  for(;;) {
      if (setjmp(env->jmp_env) == 0) {
          /* if an exception is pending, we execute it here */
      }

      next_tb = 0; /* force lookup of first TB */
      for(;;) {
          interrupt_request = env->interrupt_request;
          if (unlikely(interrupt_request)) {

          }

          tb = tb_find_fast(env);

          if (next_tb != 0 && tb->page_addr[1] == -1) {
              tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
          }

          if (likely(!env->exit_request)) {
                tc_ptr = tb->tc_ptr;
              /* execute the generated code */
                next_tb = tcg_qemu_tb_exec(env, tc_ptr);
          } 
      }
  }

tb_add_jump does block chaining. The variable names next_tb and tb
could be misleading here. tb_add_jump will link next_tb to tb, i.e.,
next_tb -> tb. And QEMU use the last two bit of the pointer to
TranslationBlock to encode the direction of the block chaining.
For example, next_tb[0] might be the if branch, and next_tb[1]
might be the else branch.

  Block chaining can be done direct or indirect. Direct means you patch
the translated code in the tranlation code cache, so that it'll jump
to next translated code block then executed. Indirect means you use
TranslationBlock tb_next field to point to next translated code block
in the tranlation code cache. On host like x86 and arm, direct block
chaining is used.

  Also note that while QEMU generate host binary from TCG IR, it will
leave some space for further block chaining to do the patch.


Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[Lei Li]

On 09/22/2011 09:58 AM, 陳韋任 wrote:

>>       /* list of TBs jumping to this one. This is a circular list using
>>          the two least significant bits of the pointers to tell what is
>>          the next pointer: 0 = jmp_next[0], 1 = jmp_next[1], 2 =
>>          jmp_first */
>>       struct TranslationBlock *jmp_next[2];
>>       struct TranslationBlock *jmp_first;
>    After tracing the code, I found the comment might be wrong.
> For example, if we link tb1 to tb2, i.e., tb1 ->  tb2. Then
> "tb1->jmp_next[n] = tb2" and "tb2->jmp_first = tb1" (roughly
> speaking). I'm not sure if I misunderstand the comment "list
> of TBs jumping to this one", or it is just wrong.
Well, the comment is from source code. I don't catch why you think "list
of TBS jumping to this one" is wrong.
My understand is that TB chain be used forreduce  switch  from the  translation
cache  to the  guest code. It will be a circular list if there is no interrupt
or exceptional.
At mean while, it's just the date related to TB chain in TB struct, it's
not about process of how TB chain work.

> Regards,
> chenwj
>

-- 
Lei

Re: [Qemu-devel] TB chaining

[陳韋任]

> Well, the comment is from source code. I don't catch why you think "list
> of TBS jumping to this one" is wrong.
> My understand is that TB chain be used forreduce  switch  from the  translation
> cache  to the  guest code. It will be a circular list if there is no interrupt
> or exceptional.
> At mean while, it's just the date related to TB chain in TB struct, it's
> not about process of how TB chain work.

  "list of TBs jumping to this one" make me think that jmp_next and
jmp_first store those TBs jump to this TB. But it seems the actual
use of jmp_next is another way around, jmp_next points to those TBs
next to this one.

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[Xin Tong]

[-- Attachment #1: Type: text/plain, Size: 1061 bytes --]

if direct chaining is used, am I right to think that jmp_next and jmp_first
will not be used ?

Thanks

Xin


On Wed, Sep 21, 2011 at 10:36 PM, 陳韋任 <chenwj@iis.sinica.edu.tw> wrote:

> > Well, the comment is from source code. I don't catch why you think "list
> > of TBS jumping to this one" is wrong.
> > My understand is that TB chain be used forreduce  switch  from the
>  translation
> > cache  to the  guest code. It will be a circular list if there is no
> interrupt
> > or exceptional.
> > At mean while, it's just the date related to TB chain in TB struct, it's
> > not about process of how TB chain work.
>
>   "list of TBs jumping to this one" make me think that jmp_next and
> jmp_first store those TBs jump to this TB. But it seems the actual
> use of jmp_next is another way around, jmp_next points to those TBs
> next to this one.
>
> Regards,
> chenwj
>
> --
> Wei-Ren Chen (陳韋任)
> Computer Systems Lab, Institute of Information Science,
> Academia Sinica, Taiwan (R.O.C.)
> Tel:886-2-2788-3799 #1667
>
>

[-- Attachment #2: Type: text/html, Size: 1522 bytes --]

Re: [Qemu-devel] TB chaining

[陳韋任]

> if direct chaining is used, am I right to think that jmp_next and jmp_first
> will not be used ?

  You have to know that when we say "TB", it might means different
things according to the context.

  QEMU use struct TranslationBlock to record some information about
TB in the code cache. Take direct block chaining for example, when
I say we direct link tb1 to tb2, i.e., tb1 -> tb2, that actually
means two things. First, we patch the branch target of tb1 (in the
code cache) so that tb1 can jump to tb2 (in the code cache) and
executed. Meanwhile, we need to update tb1 (struct TranslationBlock)
and tb2 (struct TranslationBlock) to reflect the fact that tb1 (in the
code cache) is linked to tb2 (in the code cache). jmp_next and jmp_first
are fields of struct TranslationBlock, we use them when we need to
unchian TBs (in the code cache).

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[陳韋任]

> I see, so they (jmp_next, jmp_first) are just for finding the tbs when
> unchaining is needed. do they have any other uses? also, does QEMU do inline
> caching ( when it is a conditional branch)?

  Yes, they are used for unchaining. Please see cpu_unlink_tb ->
tb_reset_jump_recursive.

  What "inline caching" means? When it's a conditional branch, the
branch target is fixed, and here comes the direct block chaining.
There is another dynamic translation technique called IBTC (indirect
branch translation cache) for indirect branch which has no fixed
branch target. But QEMU doesn't has IBTC. Could you please explain
what "inline caching" is?

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[Xin Tong]

[-- Attachment #1: Type: text/plain, Size: 1496 bytes --]

Say the

On Fri, Sep 23, 2011 at 10:50 PM, 陳韋任 <chenwj@iis.sinica.edu.tw> wrote:

> > I see, so they (jmp_next, jmp_first) are just for finding the tbs when
> > unchaining is needed. do they have any other uses? also, does QEMU do
> inline
> > caching ( when it is a conditional branch)?
>
>   Yes, they are used for unchaining. Please see cpu_unlink_tb ->
> tb_reset_jump_recursive.
>
>  What "inline caching" means? When it's a conditional branch, the
>

Say your are trying to emulate an indirect jump ( i.e. jmp eax). Because eax
is unknown at compile time, you will have to return to the mainloop to look
it up. However, if you know some likely values, you can do a few cached
compare and hope it hits one of them.

compare eax = 0x33e3e23
   jmp tb 30
compare eax = 0332d2ed
  jmp tb 30
tb exit



> branch target is fixed, and here comes the direct block chaining.
>

If the branch target is fix, you will still need 2 jmps, one for taken
branch another for nottaken branch. can you show me where the code does that
is ?



> There is another dynamic translation technique called IBTC (indirect
> branch translation cache) for indirect branch which has no fixed
> branch target. But QEMU doesn't has IBTC. Could you please explain
> what "inline caching" is?
>
> Regards,
> chenwj
>
> --
> Wei-Ren Chen (陳韋任)
> Computer Systems Lab, Institute of Information Science,
> Academia Sinica, Taiwan (R.O.C.)
> Tel:886-2-2788-3799 #1667
>

[-- Attachment #2: Type: text/html, Size: 2284 bytes --]

Re: [Qemu-devel] TB chaining

[陳韋任]

> Say your are trying to emulate an indirect jump ( i.e. jmp eax). Because eax
> is unknown at compile time, you will have to return to the mainloop to look
> it up. However, if you know some likely values, you can do a few cached
> compare and hope it hits one of them.
> 
> compare eax = 0x33e3e23
>    jmp tb 30
> compare eax = 0332d2ed
>   jmp tb 30
> tb exit

  I believe we are talking about the same thing. :-) The terminology
"IBTC" is coined by "Evaluating Indirect Branch Handling Mechanisms
in Software Dynamic Translation Systems". QEMU does not implement
IBTC or inline caching.

> If the branch target is fix, you will still need 2 jmps, one for taken
> branch another for nottaken branch. can you show me where the code does that
> is ?

  Take x86 for example, see gen_goto_tb (target-i386/translate.c).
gen_goto_tb generates TCG IR for block chaining. Here is the code
snip of gen_goto_tb.

    tcg_gen_goto_tb(tb_num); // tb_num could be taken or nottaken branch

    gen_jmp_im(eip);

    tcg_gen_exit_tb((tcg_target_long)tb + tb_num);

How block chaining is done is a little complicate. You can refer to the
white paper "Porting QEMU to Plan 9: QEMU Internals and Port Strategy"
to get a general idea.

  HTH.

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667

Re: [Qemu-devel] TB chaining

[Xin Tong]

I came back to the block chaining code. This code is still not very
clear to me. Here we are linking tb_next -> tb. jmp_next of the tb
contains the next tbs it will jump to. why are we checking the
!tb->jmp_next[n], but not !tb_next->jmp_next[n] ?

static inline void tb_add_jump(TranslationBlock *tb, int n,
                               TranslationBlock *tb_next)
{
    if (!tb->jmp_next[n]) {
        /* patch the native jump address */
        tb_set_jmp_target(tb, n, (unsigned long)tb_next->tc_ptr);

        /* add in TB jmp circular list */
        tb->jmp_next[n] = tb_next->jmp_first;
        tb_next->jmp_first = (TranslationBlock *)((long)(tb) | (n));
    }
}


Thanks a lot

Xin


On Sat, Sep 24, 2011 at 7:16 AM, 陳韋任 <chenwj@iis.sinica.edu.tw> wrote:
>> Say your are trying to emulate an indirect jump ( i.e. jmp eax). Because eax
>> is unknown at compile time, you will have to return to the mainloop to look
>> it up. However, if you know some likely values, you can do a few cached
>> compare and hope it hits one of them.
>>
>> compare eax = 0x33e3e23
>>    jmp tb 30
>> compare eax = 0332d2ed
>>   jmp tb 30
>> tb exit
>
>  I believe we are talking about the same thing. :-) The terminology
> "IBTC" is coined by "Evaluating Indirect Branch Handling Mechanisms
> in Software Dynamic Translation Systems". QEMU does not implement
> IBTC or inline caching.
>
>> If the branch target is fix, you will still need 2 jmps, one for taken
>> branch another for nottaken branch. can you show me where the code does that
>> is ?
>
>  Take x86 for example, see gen_goto_tb (target-i386/translate.c).
> gen_goto_tb generates TCG IR for block chaining. Here is the code
> snip of gen_goto_tb.
>
>    tcg_gen_goto_tb(tb_num); // tb_num could be taken or nottaken branch
>
>    gen_jmp_im(eip);
>
>    tcg_gen_exit_tb((tcg_target_long)tb + tb_num);
>
> How block chaining is done is a little complicate. You can refer to the
> white paper "Porting QEMU to Plan 9: QEMU Internals and Port Strategy"
> to get a general idea.
>
>  HTH.
>
> Regards,
> chenwj
>
> --
> Wei-Ren Chen (陳韋任)
> Computer Systems Lab, Institute of Information Science,
> Academia Sinica, Taiwan (R.O.C.)
> Tel:886-2-2788-3799 #1667
>

Re: [Qemu-devel] TB chaining

[陳韋任]

On Thu, Nov 24, 2011 at 08:54:36PM -0500, Xin Tong wrote:
> I came back to the block chaining code. This code is still not very
> clear to me. Here we are linking tb_next -> tb. jmp_next of the tb
> contains the next tbs it will jump to. why are we checking the
> !tb->jmp_next[n], but not !tb_next->jmp_next[n] ?
> 
> static inline void tb_add_jump(TranslationBlock *tb, int n,
>                                TranslationBlock *tb_next)
> {
>     if (!tb->jmp_next[n]) {
>         /* patch the native jump address */
>         tb_set_jmp_target(tb, n, (unsigned long)tb_next->tc_ptr);
> 
>         /* add in TB jmp circular list */
>         tb->jmp_next[n] = tb_next->jmp_first;
>         tb_next->jmp_first = (TranslationBlock *)((long)(tb) | (n));
>     }
> }

  Maybe I talked about TB chaining wrong before. The variable names in
QEMU could be misleading. next_tb and tb_next are _different_ things.
Let's see cpu_exec (cpu-exec.c) which calls tb_add_jump first.

  // TB chaining direction: next_tb -> tb
  if (next_tb != 0 && tb->page_addr[1] == -1) {
      tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
  }

Then let's see tb_add_jump.

  // TB chaining direction: tb -> tb_next
  static inline void tb_add_jump(TranslationBlock *tb, int n,
                                 TranslationBlock *tb_next)
  {
      if (!tb->jmp_next[n]) {
          /* patch the native jump address */
          tb_set_jmp_target(tb, n, (unsigned long)tb_next->tc_ptr);

          /* add in TB jmp circular list */
          tb->jmp_next[n] = tb_next->jmp_first;
          tb_next->jmp_first = (TranslationBlock *)((long)(tb) | (n));
      }
  }

QEMU uses jmp_next and jmp_first to record the TB chaining status. I
think visual presentation can help you understand how this is working.
Here you go,
  http://people.cs.nctu.edu.tw/~chenwj/slide/QEMU/QEMU%20-%20block%20chaining.ppt

P.S. In case you know chinese, you can see the articles on
     http://www.hellogcc.org/ (search tag qemu).

Regards,
chenwj

-- 
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj