[Qemu-devel] Storing code caching

[Qemu-devel] Storing code caching

[Martin Williams]

Has anyone thought about trying to store the code caching on disk?
I am thinking of one file which contains the blocks of code that qemu 
compiles at run time, and another which has locations (within the file? 
locations from the base of where the application is launched in memory, 
not sure which would work best) of where these blocks start from. Qemu 
would then look for a .codecache at launch, then look inside the 
location list file when it wants a code block, then load it from the 
other file (obviously both files would be held in RAM).

Obviously this would be most effective if the .codecache files were 
generated in advance rather than saved retrospectively as qemu runs.

I would be willing to start writing a tool to generate the codecache 
files, however I was wondering what the developers think on the 
subject, and whether it is possible with qemu's current architechure 
etc, and whether the current qemu core is adaptable to generate the 
blocks the utility to save, etc.

Any thoughts, criticisms, suggestions, etc (including if I am beating 
down the wrong track and this is actually impossible) - just a thought 
to try and speed execution up in User Mode.

Martin

Re: [Qemu-devel] Storing code caching

[John R. Hogerhuis]

On Thu, 2004-07-08 at 05:26, Martin Williams wrote:
> Has anyone thought about trying to store the code caching on disk?

Are you talking about "save machine state" essentially "suspend/resume?"
That is certainly possible and I believe it has been discussed on the
list.

The other possibility, that you wish to permanently associate
untranslated code with translated code by having a big cache available
on disk is in the general case "the halting problem" and there can be no
algorithm for that. So you've been warned: There Be Dragons Here...

However this is real life so there are probably some things you can do.

Some things to understand:

1. Basic blocks of code in the cache are found by their addresses in
memory, not their content. You can imagine that from one run to the next
code would load in different spots in memory. I suppose you could come
up with a set of heuristics for recognizing a basic block:
a) the location is not permanent but it might be a good clue. Perhaps
though with virtual address space programs always locate to the same
place in a virtual map though they will be different spots in physical
map?
b) the length of the block never changes. That could be a good heuristic
c) A checksum of the code with consideration for absolute addresses that
have been "fixed up" in the code. These addresses may be different from
run-to-run. Remember though adding in a checksum is an efficiency
tradeoff. It may not be worth it.
d) self modifying code, self modifying code, self modifying code...

In coming up with heuristics for recognizing already translated code
available in the cache, remember you are trading off against just
retranslating. Depending on the complexity/resource intensivity of
computations for your heuristic it may not be worth it to do the
computations.

If you think hard about it there are probably some things you could do
efficiently to reuse basic blocks from previous runs. "User mode" QEMU
is probably an easier case than the general one of running an entire OS
image. And maybe you would want to look at load time... When given a
program to run you check your on disk cache to see if you have loaded
this program before. Checksum it once to see if you have already saved a
cache image for this program. If so, load it up. Encountering
dynamically translated (invalidated cache) portions of the code will
result in "dead areas" which should never be cached.

Anyway an interesting problem for a grad student, I'd say... you have
some prototyping/analysis to do in order to come up with some heuristics
for matching up real code with cached code.

-- John.

Re: [Qemu-devel] Storing code caching

[Antony T Curtis]

On Thu, 2004-07-08 at 18:05, John R. Hogerhuis wrote:
> On Thu, 2004-07-08 at 05:26, Martin Williams wrote:
> > Has anyone thought about trying to store the code caching on disk?
> 
> Are you talking about "save machine state" essentially "suspend/resume?"
> That is certainly possible and I believe it has been discussed on the
> list.

<snip>

I think a more interesting idea is to 'virtualize' the memory.... That
is, we provide a means for a guest to request more physical memory and
to be able to release that memory back to the host... Perhaps also some
method in which the host can warn the guest of low memory situations so
that the guest can be more aggressive on memory reclaiming.

Of course, this optimization would require changes to the guest OS to
take advantage of it but it would mean that the guest would no longer
have to worry about swap pressures and that the host can perform the
swapping on behalf of the guest - this would be much faster as the
guest's virtual hardware will be much slower to swap to than the hosts'
real hardware.

This communication mechinism has to be well defined and audited as it
could potentially allow the guest the ability to 'break out' of it's
box. I would suggest that the best way would be to make the
communication channel look like some piece of hardware - but there are
other options available - such as magic opcodes...

-- 
Antony T Curtis <antony.t.curtis@ntlworld.com>

Re: [Qemu-devel] Storing code caching

[Martin Williams]

Hmm,

My initial idea was that once code is loaded (as I understand it - 
please correct me if I am utterly wrong) is that when a program loads, 
the memory is uses starts at a certain location, and that all code 
inside the program is consistently located at a relative address from 
that location. (Could someone who really knows about this sort of thing 
please advise?!?)

My idea is to write a program that caches individual files code (rather 
than everything) - based around the idea that when a block is started 
executing, the cache would be accessed and address minus the base 
address (in other words the offset of the block) would be used to find 
it within the cache (some algorithm is needed for an efficient method 
of storing and locating these blocks as they will not be the same size 
as the originals). The basic idea would then be that once qemu detects 
a self modifying piece of code, (by a write to a memory address), it 
would then black list the block in which the write happened (is this 
possible?).

The program I would write would basically use the qemu core to process 
an entire executable, creating the blocks that are executable on the 
host machine, and store them. Then start work on modifying qemu to 
recognise the existense of the cache file and use the blocks. Then deal 
with the self-modyfing code issue as above ...

Martin

PS - I'm a CS undergrad, but I'm game for it anyway :)

On 8 Jul 2004, at 18:05, John R. Hogerhuis wrote:

> On Thu, 2004-07-08 at 05:26, Martin Williams wrote:
>> Has anyone thought about trying to store the code caching on disk?
>
> Are you talking about "save machine state" essentially 
> "suspend/resume?"
> That is certainly possible and I believe it has been discussed on the
> list.
>
> The other possibility, that you wish to permanently associate
> untranslated code with translated code by having a big cache available
> on disk is in the general case "the halting problem" and there can be 
> no
> algorithm for that. So you've been warned: There Be Dragons Here...
>
> However this is real life so there are probably some things you can do.
>
> Some things to understand:
>
> 1. Basic blocks of code in the cache are found by their addresses in
> memory, not their content. You can imagine that from one run to the 
> next
> code would load in different spots in memory. I suppose you could come
> up with a set of heuristics for recognizing a basic block:
> a) the location is not permanent but it might be a good clue. Perhaps
> though with virtual address space programs always locate to the same
> place in a virtual map though they will be different spots in physical
> map?
> b) the length of the block never changes. That could be a good 
> heuristic
> c) A checksum of the code with consideration for absolute addresses 
> that
> have been "fixed up" in the code. These addresses may be different from
> run-to-run. Remember though adding in a checksum is an efficiency
> tradeoff. It may not be worth it.
> d) self modifying code, self modifying code, self modifying code...
>
> In coming up with heuristics for recognizing already translated code
> available in the cache, remember you are trading off against just
> retranslating. Depending on the complexity/resource intensivity of
> computations for your heuristic it may not be worth it to do the
> computations.
>
> If you think hard about it there are probably some things you could do
> efficiently to reuse basic blocks from previous runs. "User mode" QEMU
> is probably an easier case than the general one of running an entire OS
> image. And maybe you would want to look at load time... When given a
> program to run you check your on disk cache to see if you have loaded
> this program before. Checksum it once to see if you have already saved 
> a
> cache image for this program. If so, load it up. Encountering
> dynamically translated (invalidated cache) portions of the code will
> result in "dead areas" which should never be cached.
>
> Anyway an interesting problem for a grad student, I'd say... you have
> some prototyping/analysis to do in order to come up with some 
> heuristics
> for matching up real code with cached code.
>
> -- John.
>
>
>
> _______________________________________________
> Qemu-devel mailing list
> Qemu-devel@nongnu.org
> http://lists.nongnu.org/mailman/listinfo/qemu-devel
>

Re: [Qemu-devel] Storing code caching

[John R. Hogerhuis]

On Thu, 2004-07-08 at 10:57, Martin Williams wrote:

> My idea is to write a program that caches individual files code (rather 
> than everything) - based around the idea that when a block is started 
> executing, the cache would be accessed and address minus the base 
> address (in other words the offset of the block) would be used to find 
> it within the cache (some algorithm is needed for an efficient method 
> of storing and locating these blocks as they will not be the same size 
> as the originals). The basic idea would then be that once qemu detects 
> a self modifying piece of code, (by a write to a memory address), it 
> would then black list the block in which the write happened (is this 
> possible?).
> 

Again... are you talking about User Mode QEMU where you are only running
one program + libraries or are you talking about QEMU running an
operating system?

I can imagine in running an OS you are going to get a lot of collisions
where two blocks are at the same offset. Throw in the length of the
block and I suppose you will have a lot less but I would guess it will
still happen enough to be a problem. You'll have to try and see. The
difference between the regular QEMU cache and one saved to disk is that
the segment selectors are not valid across runs.

In any event, if you do get a collision you can do a memcmp to see if
they are really the same exact thing. The trick is to have good enough
heurisitics that you don't do the memcmp very often.

> The program I would write would basically use the qemu core to process 
> an entire executable, creating the blocks that are executable on the 
> host machine, and store them. Then start work on modifying qemu to 
> recognise the existense of the cache file and use the blocks. Then deal 
> with the self-modyfing code issue as above ...
> 

QEMU loads the binary to RAM and builds the cache as it simulates its
execution. Working from a executable file without simulating is a bit
different. For that you should probably look into how a disassembler
works and also realize you have a lot of reworking to do if you want to
take the approach. I wouldn't, unless your goal is to be able to
actually make a new shippable translated binary image. If you are
looking to do that, I think that's, well... ambitious would be the nice
word.

> Martin
> 
> PS - I'm a CS undergrad, but I'm game for it anyway :)

Well that just means you can attack the halting problem with more
optimism than some of the other folks here ;-)  Actually when people
bring that up you just need to keep in mind that it is theory.
Important, but in engineering the solution just has to meet the
threshold of "good enough."

Re: [spam score 1/10 -pobox] Re: [Qemu-devel] Storing code caching

[John R. Hogerhuis]

On Thu, 2004-07-08 at 10:25, Antony T Curtis wrote:
> On Thu, 2004-07-08 at 18:05, John R. Hogerhuis wrote:
> > On Thu, 2004-07-08 at 05:26, Martin Williams wrote:
> > > Has anyone thought about trying to store the code caching on disk?
> > 
> > Are you talking about "save machine state" essentially "suspend/resume?"
> > That is certainly possible and I believe it has been discussed on the
> > list.
> 
> <snip>
> 
> I think a more interesting idea is to 'virtualize' the memory.... That
> is, we provide a means for a guest to request more physical memory and
> to be able to release that memory back to the host... Perhaps also some
> method in which the host can warn the guest of low memory situations so
> that the guest can be more aggressive on memory reclaiming.
> 

Hmm... you're trying to tell me something, aren't you? ;-)

You'll need to connect the dots for the feeble-minded like myself.

How does this relate to persisting translated code (or
save-machine-state)?

-- John.

Re: [Qemu-devel] Storing code caching

[Julian Seward]

> The program I would write would basically use the qemu core to process
> an entire executable, creating the blocks that are executable on the
> host machine, and store them. Then start work on modifying qemu to
> recognise the existense of the cache file and use the blocks. Then deal
> with the self-modyfing code issue as above ...

Nice idea, but ... I suspect it solves a non-problem really.  Caching
translations is only worthwhile when translation time is a large
part of overall run time, but I bet that's not the case.  It certainly
isn't with Valgrind, which uses similar technology.

If you want to throw lots of hacking effort at QEMU to make it
go faster, I suspect you'll need to be building a more sophisticated
code generator, a la "lcc" (http://www.cs.princeton.edu/software/lcc).
That's a lot of work, though.

J

Re[2]: [Qemu-devel] Storing code caching

[Igor Shmukler]

> I think a more interesting idea is to 'virtualize' the memory.... That
> is, we provide a means for a guest to request more physical memory and
> to be able to release that memory back to the host... Perhaps also some
> method in which the host can warn the guest of low memory situations so
> that the guest can be more aggressive on memory reclaiming.
> 
> Of course, this optimization would require changes to the guest OS to
> take advantage of it but it would mean that the guest would no longer
> have to worry about swap pressures and that the host can perform the
> swapping on behalf of the guest - this would be much faster as the
> guest's virtual hardware will be much slower to swap to than the hosts'
> real hardware.
> 
> This communication mechinism has to be well defined and audited as it
> could potentially allow the guest the ability to 'break out' of it's
> box. I would suggest that the best way would be to make the
> communication channel look like some piece of hardware - but there are
> other options available - such as magic opcodes...

VMWare developed a solution for this issue a while ago. They described a technique called balooning at the OSDI'02. Their approach allows to address issues you raised without modifications to the guest OS.
All the is needed is a baloon driver.

I don't see how it would help with caching execution profile, though.

IS.

Re: [Qemu-devel] Storing code caching

[John R. Hogerhuis]

On Thu, 2004-07-08 at 12:11, Julian Seward wrote:

> Nice idea, but ... I suspect it solves a non-problem really.  Caching
> translations is only worthwhile when translation time is a large
> part of overall run time, but I bet that's not the case.  It certainly
> isn't with Valgrind, which uses similar technology.
> 

Right. That's entirely possible, but just as much speculation without
any numbers.

No one knows until the work or analysis is done...

Translation time is certainly not negligible. And a better code
generator would quite likely swamp any improvements a persistent cache
could give. There's disk I/O to consider there too. But it is possible
the improvements would make a faster emulator.

It depends on requirements too I guess. If you don't care about load
time then you probably don't care about translation time either since
from the user's point of view they are going to be conflated.

> If you want to throw lots of hacking effort at QEMU to make it
> go faster, I suspect you'll need to be building a more sophisticated
> code generator, a la "lcc" (http://www.cs.princeton.edu/software/lcc).

Interesting... why do you bring up lcc specifically? Just browsing that
page and its FAQ didn't tell me much about it other than it is a
retargetable C compiler.