[Qemu-devel] Time complexity for self-modifying code

[Qemu-devel] Time complexity for self-modifying code

[Michael Gagnon]

Hello.  I'm a student at George Mason University and I had a question 
regarding the time complexity of QEMU's algorithm for dealing with 
self-modifying code. 

 From looking at the QEMU Internals documentation 
(http://fabrice.bellard.free.fr/qemu/qemu-tech.html), it seems that 
QEMU's method for handling self-modifying code might have different 
algorithmic efficiency classes for it's average case and worst case.  As 
in, on average I assume that QEMU emulates instructions at O(n) 
efficiency.  In the worst-case, might self-modifying code change the 
efficiency of QEMU to another order of efficiency, such as O(n^2)?  Any 
thoughts would be greatly appreciated.  Thanks!

Mike Gagnon
http://www.mikegagnon.com

Re: [Qemu-devel] Time complexity for self-modifying code

[Paul Brook]

On Thursday 08 February 2007 20:01, Michael Gagnon wrote:
> Hello.  I'm a student at George Mason University and I had a question
> regarding the time complexity of QEMU's algorithm for dealing with
> self-modifying code.
>
>  From looking at the QEMU Internals documentation
> (http://fabrice.bellard.free.fr/qemu/qemu-tech.html), it seems that
> QEMU's method for handling self-modifying code might have different
> algorithmic efficiency classes for it's average case and worst case.  As
> in, on average I assume that QEMU emulates instructions at O(n)
> efficiency.  In the worst-case, might self-modifying code change the
> efficiency of QEMU to another order of efficiency, such as O(n^2)?  Any
> thoughts would be greatly appreciated.  Thanks!

Depends what your N is.

Worst case for SMC (Self Modifying Code) is modifying code in the same TB 
(Translation Block) as the store instruction. This kind of fault requires 
O(tb_size) time, so executing a TB (assuming every insn traps) takes 
O(tb_size ^2) time.  However the page boundaries impose a hard limit on the 
size of a TB. 

Thus for N < TARGET_PAGE_SIZE worst case total execution time is O(N^2), but 
for N > TARGET_PAGE_SIZE total execution time is still O(N).

For SMC the constant factor may be orders of magnitude larger than for regular 
code.

Paul