* [Qemu-devel] TB chaining @ 2011-09-21 23:05 Xin Tong 2011-09-22 1:37 ` Lei Li 2011-09-22 2:15 ` 陳韋任 0 siblings, 2 replies; 13+ messages in thread From: Xin Tong @ 2011-09-21 23:05 UTC (permalink / raw) To: qemu-devel [-- 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 --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-21 23:05 [Qemu-devel] TB chaining Xin Tong @ 2011-09-22 1:37 ` Lei Li 2011-09-22 1:58 ` 陳韋任 2011-09-22 2:15 ` 陳韋任 1 sibling, 1 reply; 13+ messages in thread From: Lei Li @ 2011-09-22 1:37 UTC (permalink / raw) To: Xin Tong; +Cc: qemu-devel 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-22 1:37 ` Lei Li @ 2011-09-22 1:58 ` 陳韋任 2011-09-22 2:27 ` Lei Li 0 siblings, 1 reply; 13+ messages in thread From: 陳韋任 @ 2011-09-22 1:58 UTC (permalink / raw) To: Lei Li; +Cc: qemu-devel, Xin Tong > /* 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-22 1:58 ` 陳韋任 @ 2011-09-22 2:27 ` Lei Li 2011-09-22 2:36 ` 陳韋任 0 siblings, 1 reply; 13+ messages in thread From: Lei Li @ 2011-09-22 2:27 UTC (permalink / raw) To: 陳韋任; +Cc: qemu-devel, Xin Tong 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-22 2:27 ` Lei Li @ 2011-09-22 2:36 ` 陳韋任 2011-09-22 12:41 ` Xin Tong 0 siblings, 1 reply; 13+ messages in thread From: 陳韋任 @ 2011-09-22 2:36 UTC (permalink / raw) To: Lei Li; +Cc: qemu-devel > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-22 2:36 ` 陳韋任 @ 2011-09-22 12:41 ` Xin Tong 2011-09-23 2:14 ` 陳韋任 0 siblings, 1 reply; 13+ messages in thread From: Xin Tong @ 2011-09-22 12:41 UTC (permalink / raw) To: 陳韋任; +Cc: Lei Li, qemu-devel [-- 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 --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-22 12:41 ` Xin Tong @ 2011-09-23 2:14 ` 陳韋任 [not found] ` <CALKntY2XeOc1LUE0NGXy_CKUer9+gxQykYC5hDzJnskx+OfdCQ@mail.gmail.com> 0 siblings, 1 reply; 13+ messages in thread From: 陳韋任 @ 2011-09-23 2:14 UTC (permalink / raw) To: Xin Tong; +Cc: Lei Li, 陳韋任, qemu-devel > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
[parent not found: <CALKntY2XeOc1LUE0NGXy_CKUer9+gxQykYC5hDzJnskx+OfdCQ@mail.gmail.com>]
* Re: [Qemu-devel] TB chaining [not found] ` <CALKntY2XeOc1LUE0NGXy_CKUer9+gxQykYC5hDzJnskx+OfdCQ@mail.gmail.com> @ 2011-09-24 2:50 ` 陳韋任 2011-09-24 10:36 ` Xin Tong 0 siblings, 1 reply; 13+ messages in thread From: 陳韋任 @ 2011-09-24 2:50 UTC (permalink / raw) To: Xin Tong; +Cc: qemu-devel > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-24 2:50 ` 陳韋任 @ 2011-09-24 10:36 ` Xin Tong 2011-09-24 11:16 ` 陳韋任 0 siblings, 1 reply; 13+ messages in thread From: Xin Tong @ 2011-09-24 10:36 UTC (permalink / raw) To: 陳韋任; +Cc: qemu-devel [-- 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 --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-24 10:36 ` Xin Tong @ 2011-09-24 11:16 ` 陳韋任 2011-11-25 1:54 ` Xin Tong 0 siblings, 1 reply; 13+ messages in thread From: 陳韋任 @ 2011-09-24 11:16 UTC (permalink / raw) To: Xin Tong; +Cc: qemu-devel, 陳韋任 > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-24 11:16 ` 陳韋任 @ 2011-11-25 1:54 ` Xin Tong 2011-11-25 2:52 ` 陳韋任 0 siblings, 1 reply; 13+ messages in thread From: Xin Tong @ 2011-11-25 1:54 UTC (permalink / raw) To: 陳韋任; +Cc: qemu-devel 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 > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-11-25 1:54 ` Xin Tong @ 2011-11-25 2:52 ` 陳韋任 0 siblings, 0 replies; 13+ messages in thread From: 陳韋任 @ 2011-11-25 2:52 UTC (permalink / raw) To: Xin Tong; +Cc: qemu-devel, 陳韋任 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Qemu-devel] TB chaining 2011-09-21 23:05 [Qemu-devel] TB chaining Xin Tong 2011-09-22 1:37 ` Lei Li @ 2011-09-22 2:15 ` 陳韋任 1 sibling, 0 replies; 13+ messages in thread From: 陳韋任 @ 2011-09-22 2:15 UTC (permalink / raw) To: Xin Tong; +Cc: qemu-devel > 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2011-11-25 2:52 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-09-21 23:05 [Qemu-devel] TB chaining Xin Tong 2011-09-22 1:37 ` Lei Li 2011-09-22 1:58 ` 陳韋任 2011-09-22 2:27 ` Lei Li 2011-09-22 2:36 ` 陳韋任 2011-09-22 12:41 ` Xin Tong 2011-09-23 2:14 ` 陳韋任 [not found] ` <CALKntY2XeOc1LUE0NGXy_CKUer9+gxQykYC5hDzJnskx+OfdCQ@mail.gmail.com> 2011-09-24 2:50 ` 陳韋任 2011-09-24 10:36 ` Xin Tong 2011-09-24 11:16 ` 陳韋任 2011-11-25 1:54 ` Xin Tong 2011-11-25 2:52 ` 陳韋任 2011-09-22 2:15 ` 陳韋任
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.