From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1HFG1c-00041G-7U for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:37:48 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1HFG1Y-00040j-OG for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:37:47 -0500 Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1HFG1Y-00040g-IB for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:37:44 -0500 Received: from mail.codesourcery.com ([65.74.133.4]) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA:32) (Exim 4.52) id 1HFG1X-0004Zl-W4 for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:37:44 -0500 From: Paul Brook Subject: Re: [Qemu-devel] Time complexity for self-modifying code Date: Thu, 8 Feb 2007 20:37:36 +0000 References: <45CB81B5.9080405@gmu.edu> In-Reply-To: <45CB81B5.9080405@gmu.edu> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200702082037.36905.paul@codesourcery.com> Reply-To: qemu-devel@nongnu.org List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: Michael Gagnon 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