Implementing split memory in Xen is annoyingly hard?

Implementing split memory in Xen is annoyingly hard?

[Sina Bahram]

Hi all,

This might end up being one of my last posts on this topic, as I think I've
determined that what I'd like to do with Xen is quite annoyingly hard for
now. If anyone could please either verify or poke some holes in what I'm
about to say, I'd very much appreciate that.

Let's assume shadow page tables are in use.

#1: Xen can mirror the guest's page table in its shadow page table because
it marks all the guest pages as read only; thus, when a page fault is
generated as a result of a write, it can allow the write to happen, while
quickly updating its own copy at the same time.

#2: Xen absolutely does not, (can not?), cause a fault or other VM exit to
be generated upon an execute or a read of a page.

#3: Since I wish to implement split memory, (Harvard Architecture), I have
to have the ability to intercept all of one of two different classes of
operations. Either I have to intercept all reads and writes, or I have to
intercept all executes.

#4: Since the best I can do is only intercept all writes, not all reads to
go along with that particular class of operation, I can't implement split
memory, (Harvard Architecture), in Xen.

One potential work around:

I could mark every single page of the guest's kernel as NX, and then when
that fault happens, I could then be privy to all executes from within Xen.

Is this an accurate understanding of the situation?

The following links are a subset of what I've been reading to arrive at this
conclusion:

1. https://wiki.cs.dartmouth.edu/nihal/doku.php/xen:memory
2. http://www.anandtech.com/weblog/showpost.aspx?i=467
3.
http://www.intel.com/technology/itj/2006/v10i3/3-xen/4-extending-with-intel-
vt.htm
4. http://forums.amd.com/devblog/blogpost.cfm?catid=317&threadid=104671
5. www.cc.gatech.edu/research/reports/GT-CS-08-09.pdf
6. www.usenix.org/publications/login/2007-02/pdfs/hand.pdf 

Take care,
Sina

Re: Implementing split memory in Xen is annoyingly hard?

[Keir Fraser]

On 12/12/2008 06:47, "Sina Bahram" <sbahram@nc.rr.com> wrote:

> #2: Xen absolutely does not, (can not?), cause a fault or other VM exit to
> be generated upon an execute or a read of a page.

It's not possible to make a page executable but not readable, so indeed I
think you're stumped there, unless you can work out a hackish way to
desynchronise the iTLB and the dTLB (an operation not supported
architecturally by x86 of course).

 -- Keir

RE: Implementing split memory in Xen is annoyingly hard?

[Sina Bahram]

I'm not trying to make the page executable  but not readable, as long as I
can trap all reads, that's all.

I'll be implementing a split TLB which will handle the fact that all
executes get shunted to a "split page".

Another way of saying that is that if someone looks up a virtual address, it
gets translated to one physical address if it's for read/writes and to
another one for executes. Sure one can execute the page that is read/write
and someone could read/write to the page that is execute, but it will never
happen because I'd never translate it that way in my code.

Btw, this completely eliminates anything like lisp, javascript, or anything
else from running, as they run code they have written all the time, but
that's why I only plan on doing it for kernel pages which don't write things
that they then execute.

Hope that's more clear, and is this possible, do you think, or is my summary
in the original email accurate in that it can't be done easily in xen?

Take care,
Sina

-----Original Message-----
From: Keir Fraser [mailto:keir.fraser@eu.citrix.com] 
Sent: Friday, December 12, 2008 4:20 AM
To: Sina Bahram; xen-devel@lists.xensource.com;
xen-research@lists.xensource.com
Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
hard?

On 12/12/2008 06:47, "Sina Bahram" <sbahram@nc.rr.com> wrote:

> #2: Xen absolutely does not, (can not?), cause a fault or other VM exit to
> be generated upon an execute or a read of a page.

It's not possible to make a page executable but not readable, so indeed I
think you're stumped there, unless you can work out a hackish way to
desynchronise the iTLB and the dTLB (an operation not supported
architecturally by x86 of course).

 -- Keir

Re: Implementing split memory in Xen is annoyingly hard?

[Keir Fraser]

Well, you can trap all everything if you make the page not present.

Beyond that you can selectively make a page writable or executable, but in
these cases it will have to be readable too.

 -- Keir

On 12/12/2008 09:50, "Sina Bahram" <sbahram@nc.rr.com> wrote:

> I'm not trying to make the page executable  but not readable, as long as I
> can trap all reads, that's all.
> 
> I'll be implementing a split TLB which will handle the fact that all
> executes get shunted to a "split page".
> 
> Another way of saying that is that if someone looks up a virtual address, it
> gets translated to one physical address if it's for read/writes and to
> another one for executes. Sure one can execute the page that is read/write
> and someone could read/write to the page that is execute, but it will never
> happen because I'd never translate it that way in my code.
> 
> Btw, this completely eliminates anything like lisp, javascript, or anything
> else from running, as they run code they have written all the time, but
> that's why I only plan on doing it for kernel pages which don't write things
> that they then execute.
> 
> Hope that's more clear, and is this possible, do you think, or is my summary
> in the original email accurate in that it can't be done easily in xen?
> 
> Take care,
> Sina
> 
> -----Original Message-----
> From: Keir Fraser [mailto:keir.fraser@eu.citrix.com]
> Sent: Friday, December 12, 2008 4:20 AM
> To: Sina Bahram; xen-devel@lists.xensource.com;
> xen-research@lists.xensource.com
> Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
> hard?
> 
> On 12/12/2008 06:47, "Sina Bahram" <sbahram@nc.rr.com> wrote:
> 
>> #2: Xen absolutely does not, (can not?), cause a fault or other VM exit to
>> be generated upon an execute or a read of a page.
> 
> It's not possible to make a page executable but not readable, so indeed I
> think you're stumped there, unless you can work out a hackish way to
> desynchronise the iTLB and the dTLB (an operation not supported
> architecturally by x86 of course).
> 
>  -- Keir
> 
> 

Re: Implementing split memory in Xen is annoyingly hard?

[Tim Deegan]

At 01:47 -0500 on 12 Dec (1229046441), Sina Bahram wrote:
> #2: Xen absolutely does not, (can not?), cause a fault or other VM exit to
> be generated upon an execute or a read of a page.

Yes it can -- the thing you can't do is have a fault _only_ for reads
and not for executes as well.
 
> #3: Since I wish to implement split memory, (Harvard Architecture), I have
> to have the ability to intercept all of one of two different classes of
> operations. Either I have to intercept all reads and writes, or I have to
> intercept all executes.

Intercepting _all_ reads or _all_ executes in Xen would be so slow as to
be unuseable.  You'd be much better off starting with qemu (both in
difficulty of writing the code and in speed of the finished product).

The scheme I outlined in my other email allows you to only need a fault
when the use of a page changes -- i.e. on the first write or the first
execute.  Unfortunately it doesn't distinguish between reads and
executes, so unless Intel make a chip that supports execute-only EPT
mappings it won't be good enough to give you the Harvard-architecture
scheme you want.  (They might -- maybe someone from Intel can comment).

Cheers,

Tim.

-- 
Tim Deegan <Tim.Deegan@citrix.com>
Principal Software Engineer, Citrix Systems (R&D) Ltd.
[Company #02300071, SL9 0DZ, UK.]

Re: Implementing split memory in Xen is annoyingly hard?

[Christopher Head]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sina Bahram wrote:
[snip]
> One potential work around:
> 
> I could mark every single page of the guest's kernel as NX, and then when
> that fault happens, I could then be privy to all executes from within Xen.
[snip]

I can see three possible arrangements you might try: (1) leave the data
mapped normally and handle execution specially, (2) leave code mapped
normally and handle data specially, or (3) leave neither one mapped
normally and handle both specially. As far as I can tell, solution 2
wouldn't work at all, solution 1 has a chance of working, and solution 3
is rather pointless if either of the other two works.

I don't think it would work to leave code mapped normally and map data
specially, because execute permission implies read permission and hence
you cannot make a page executable without making it also readable.

HOWEVER, I think #1 could work. The page is normally set as readable,
writable, and not executable. When the guest attempts to execute the
page, a fault occurs. Taking a cue from the PaX patches, we observe that
there are two separate TLBs: one for code and one for data. If we can
"prime" the code TLB with the proper execution mapping and then change
the page table back to the regular data mapping, we'll be in business.
In PaX, it's the data TLB that gets primed, which is trivially easy:
just touch the page. Priming the code TLB looks rather more difficult,
since you clearly have to execute something on that page in order to do
so. However, you don't want to execute arbitrary guest code, because you
need to be able to remap the page table back to the data page after
priming the TLB!

The only way I can think of to do this is to set up the mapping as code
and then stuff a specially-chosen faulting instruction into the code
page, saving what was previously there. Return to the guest with
interrupts disabled (so there's no way for control to transfer anywhere
except the jump target). The guest sees the page table set for the code
page, loads the code TLB, and then immediately hits the faulting
instruction. The hypervisor takes over, changes the pagetable mapping
back to the data page, replaces the faulting instruction with what was
originally there, and lets the guest carry on. The code TLB now having
been primed, no additional page faults occur; further, since the
pagetable has been reset, any data accesses will load the data TLB with
the data page mapping.

This sounds really intrusive though.

Chris
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: GnuPT 2.7.2
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAklCP64ACgkQiD2svb/jCb5ICgCfV3z3jdiSpt54o7pzCj48mi/m
4wQAnjTJKPNSitFwBx/th+nsXFmR5gKF
=I0hp
-----END PGP SIGNATURE-----

RE: Implementing split memory in Xen is annoyingly hard?

[Sina Bahram]

But there's no straight forward way of making the page not exist each time,
is there?

Take care,
Sina

-----Original Message-----
From: Keir Fraser [mailto:keir.fraser@eu.citrix.com] 
Sent: Friday, December 12, 2008 4:55 AM
To: Sina Bahram; xen-devel@lists.xensource.com
Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
hard?

Well, you can trap all everything if you make the page not present.

Beyond that you can selectively make a page writable or executable, but in
these cases it will have to be readable too.

 -- Keir

On 12/12/2008 09:50, "Sina Bahram" <sbahram@nc.rr.com> wrote:

> I'm not trying to make the page executable  but not readable, as long as I
> can trap all reads, that's all.
> 
> I'll be implementing a split TLB which will handle the fact that all
> executes get shunted to a "split page".
> 
> Another way of saying that is that if someone looks up a virtual address,
it
> gets translated to one physical address if it's for read/writes and to
> another one for executes. Sure one can execute the page that is read/write
> and someone could read/write to the page that is execute, but it will
never
> happen because I'd never translate it that way in my code.
> 
> Btw, this completely eliminates anything like lisp, javascript, or
anything
> else from running, as they run code they have written all the time, but
> that's why I only plan on doing it for kernel pages which don't write
things
> that they then execute.
> 
> Hope that's more clear, and is this possible, do you think, or is my
summary
> in the original email accurate in that it can't be done easily in xen?
> 
> Take care,
> Sina
> 
> -----Original Message-----
> From: Keir Fraser [mailto:keir.fraser@eu.citrix.com]
> Sent: Friday, December 12, 2008 4:20 AM
> To: Sina Bahram; xen-devel@lists.xensource.com;
> xen-research@lists.xensource.com
> Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
> hard?
> 
> On 12/12/2008 06:47, "Sina Bahram" <sbahram@nc.rr.com> wrote:
> 
>> #2: Xen absolutely does not, (can not?), cause a fault or other VM exit
to
>> be generated upon an execute or a read of a page.
> 
> It's not possible to make a page executable but not readable, so indeed I
> think you're stumped there, unless you can work out a hackish way to
> desynchronise the iTLB and the dTLB (an operation not supported
> architecturally by x86 of course).
> 
>  -- Keir
> 
> 

RE: Implementing split memory in Xen is annoyingly hard?

[Sina Bahram]

Thank you to all who've commented on this thread.

Take care,
Sina 

-----Original Message-----
From: xen-devel-bounces@lists.xensource.com
[mailto:xen-devel-bounces@lists.xensource.com] On Behalf Of Christopher Head
Sent: Friday, December 12, 2008 5:41 AM
To: xen-devel@lists.xensource.com
Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
hard?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sina Bahram wrote:
[snip]
> One potential work around:
> 
> I could mark every single page of the guest's kernel as NX, and then when
> that fault happens, I could then be privy to all executes from within Xen.
[snip]

I can see three possible arrangements you might try: (1) leave the data
mapped normally and handle execution specially, (2) leave code mapped
normally and handle data specially, or (3) leave neither one mapped
normally and handle both specially. As far as I can tell, solution 2
wouldn't work at all, solution 1 has a chance of working, and solution 3
is rather pointless if either of the other two works.

I don't think it would work to leave code mapped normally and map data
specially, because execute permission implies read permission and hence
you cannot make a page executable without making it also readable.

HOWEVER, I think #1 could work. The page is normally set as readable,
writable, and not executable. When the guest attempts to execute the
page, a fault occurs. Taking a cue from the PaX patches, we observe that
there are two separate TLBs: one for code and one for data. If we can
"prime" the code TLB with the proper execution mapping and then change
the page table back to the regular data mapping, we'll be in business.
In PaX, it's the data TLB that gets primed, which is trivially easy:
just touch the page. Priming the code TLB looks rather more difficult,
since you clearly have to execute something on that page in order to do
so. However, you don't want to execute arbitrary guest code, because you
need to be able to remap the page table back to the data page after
priming the TLB!

The only way I can think of to do this is to set up the mapping as code
and then stuff a specially-chosen faulting instruction into the code
page, saving what was previously there. Return to the guest with
interrupts disabled (so there's no way for control to transfer anywhere
except the jump target). The guest sees the page table set for the code
page, loads the code TLB, and then immediately hits the faulting
instruction. The hypervisor takes over, changes the pagetable mapping
back to the data page, replaces the faulting instruction with what was
originally there, and lets the guest carry on. The code TLB now having
been primed, no additional page faults occur; further, since the
pagetable has been reset, any data accesses will load the data TLB with
the data page mapping.

This sounds really intrusive though.

Chris
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: GnuPT 2.7.2
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAklCP64ACgkQiD2svb/jCb5ICgCfV3z3jdiSpt54o7pzCj48mi/m
4wQAnjTJKPNSitFwBx/th+nsXFmR5gKF
=I0hp
-----END PGP SIGNATURE-----

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

RE: Implementing split memory in Xen is annoyingly hard?

[Sina Bahram]

Can I get yours and other thought son this paper?

ftp://ftp.cs.wisc.edu/paradyn/papers/Rosenblum08cspm.pdf

Similar in some sense to what we've spoke of below.

Take care,
Sina

-----Original Message-----
From: xen-devel-bounces@lists.xensource.com
[mailto:xen-devel-bounces@lists.xensource.com] On Behalf Of Christopher Head
Sent: Friday, December 12, 2008 5:41 AM
To: xen-devel@lists.xensource.com
Subject: Re: [Xen-devel] Implementing split memory in Xen is annoyingly
hard?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sina Bahram wrote:
[snip]
> One potential work around:
> 
> I could mark every single page of the guest's kernel as NX, and then when
> that fault happens, I could then be privy to all executes from within Xen.
[snip]

I can see three possible arrangements you might try: (1) leave the data
mapped normally and handle execution specially, (2) leave code mapped
normally and handle data specially, or (3) leave neither one mapped
normally and handle both specially. As far as I can tell, solution 2
wouldn't work at all, solution 1 has a chance of working, and solution 3
is rather pointless if either of the other two works.

I don't think it would work to leave code mapped normally and map data
specially, because execute permission implies read permission and hence
you cannot make a page executable without making it also readable.

HOWEVER, I think #1 could work. The page is normally set as readable,
writable, and not executable. When the guest attempts to execute the
page, a fault occurs. Taking a cue from the PaX patches, we observe that
there are two separate TLBs: one for code and one for data. If we can
"prime" the code TLB with the proper execution mapping and then change
the page table back to the regular data mapping, we'll be in business.
In PaX, it's the data TLB that gets primed, which is trivially easy:
just touch the page. Priming the code TLB looks rather more difficult,
since you clearly have to execute something on that page in order to do
so. However, you don't want to execute arbitrary guest code, because you
need to be able to remap the page table back to the data page after
priming the TLB!

The only way I can think of to do this is to set up the mapping as code
and then stuff a specially-chosen faulting instruction into the code
page, saving what was previously there. Return to the guest with
interrupts disabled (so there's no way for control to transfer anywhere
except the jump target). The guest sees the page table set for the code
page, loads the code TLB, and then immediately hits the faulting
instruction. The hypervisor takes over, changes the pagetable mapping
back to the data page, replaces the faulting instruction with what was
originally there, and lets the guest carry on. The code TLB now having
been primed, no additional page faults occur; further, since the
pagetable has been reset, any data accesses will load the data TLB with
the data page mapping.

This sounds really intrusive though.

Chris
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: GnuPT 2.7.2
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAklCP64ACgkQiD2svb/jCb5ICgCfV3z3jdiSpt54o7pzCj48mi/m
4wQAnjTJKPNSitFwBx/th+nsXFmR5gKF
=I0hp
-----END PGP SIGNATURE-----

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel