[uml-devel] The SKAS4 patch?? + ideas for 0 context-switch

[uml-devel] The SKAS4 patch?? + ideas for 0 context-switch

[BlaisorBlade]

Hi Jeff, I would like to ask you to make the current form of the SKAS4 patch, 
even if incomplete, public on the -devel mailing list, even if it is not yet 
ready; I rememeber there were some problems still to solve, but if you 
publish it, the community could help you in this. Also, you actually put it 
in the x86_64 patch, so it is almost ready! Please let us see it in its 
complete form! Btw, it seems that anyway SKAS mode is not truly SKAS (new_mm 
and PTRACE_SWITCH_MM users are removed); is this just a temporary hack or 
not?

You said you sometimes feel you have too much work to do; just ask for help! 
If you want to give some tasks away, just ask for help!

Besides this generic things, I would like to see how are you implementing it, 
and I have an idea to drop the number of context switches from 2 to 0 (no 
code yet - it is a bit hard to implement). But just now, I've read on your 
diary you planned to have only 1 process for each UML processor; would that 
guarantee 0 context-switches or not? Also, this requires coming back to 
having a 2,5G TASK_SIZE inside UML, with the upper part for the UML and the 
lower to the host process. Would you accept it?

I think this can improve performance even more than the SYSEMU patch, if I 
understand TLBs well, the 2 Context Switches removed by SYSEMU are the faster 
ones.
In detail (skip this if you got what I mean): to do a syscall, without SYSEMU 
there is a CS to the guest kernel (which invalidates tons of TLBs, i.e. is 
the heavier of all ones) + a few instruction + the two useless CS's deleted 
by SYSEMU, which invalidate a very few TLB entries (I think that only 1-2 
pages of code + data will have be accessed) + the syscall execution (using a 
lot of memory) + the final context switch to the userspace program, which 
will now take a lot of time to refill its TLB.

Basically the kernel memory is trapped in the child's one like in TT mode, but 
this is exploited to avoid any context switch between the two process, with 
lazy tlb switching, much like when switching from userspace to kernel-only 
threads (the kernel sees this need when PTRACE_SYSEMU is used and an option 
is set); plus, via segmentation (much like the exec-shield patch), it is 
prohibited from accessing the kernel memory. The hard part is the 
segmentation protection, since I need to change the whole GDT and the whole 
LDT! Plus I need help on this from someone knowing well protected mode 
details - I've understood what I say from the exec-shield patch + NASM guide 
about opcodes, which is not very much.

The idea can be resumed as (I don't know at all if it's clear):

- Kernel stands to UML guest (a userspace process) as UML guest stands to its 
interior processes.

- I.e. context switches for UML syscall are like the Linux Kernel ones with 
the 4G/4G patch; I want to use the same trick to avoid context switches on 
syscalls like the UML kernel.

-- NOW COMES THE DETAILED DESCRIPTION --

- Ok, actually: when PTRACE_SYSEMU switches to the father, before calling the 
scheduler, it changes the father->mm field so that it becomes the child's one 
(and restore it on exit); the new UML would set up children->mm so that it 
contains all father mappings (supposing they stay fixed; if not I must think 
some solution. HIGHMEM mappings are not fixed, but they are released before 
exiting from kernel context, so they are still Ok); so we have no context 
switch, and the father can happily work. The security issue can be fixed (see 
below). More over, it can access directly (like in tt mode) the child memory 
and use fault_catcher to catch faults, unlike the slow pagetable walking of 
SKAS mode (I speak for copy_{from, to}_user).

- To have the same mappings, if they are all shared (I do not hope to be so 
lucky) this can be done using the fork routine as they are; otherwise, either 
the UML kernel copies the mapping from userspace, or UML creates only shared 
mappings (which maybe is not a problem IMHO since it never forks), or I 
create a modified dup_mmap routine which treats all mappings as shared one; 
the stock fork routine, in fact, would not share the pages, but just COW 
them.

- Security: this is another problem, however I have the solution: 
segmentation. I thought to use the mechanism used by the Linux kernel to 
avoid userspace accessing addresses > PAGE_OFFSET, but at last I discovered 
it wouldn't work.

The kernel already solved this, since the kernel (if you don't use the 4G/4G 
patch) does almost exactly this for user-kernel space transition (but, in the 
UML way, it still requires context switch for timer routines, and any 
interrupt one, and this cannot be solved since the interrupt can happen while 
another process, not UML-related, is executing). The problem, however, is not 
that easy to solve: the kernel solution is by marking the 
userspace-accessible pages as accessible by userspace (ring 3) code, while 
kernel page tables are not marked so, and are therefore unaccessible.

Solution in by segmentation. DS points to a struct desc_struct in memory 
(which is decoded by the CPU) which can say: refuse access to virtual 
addresses > 2,5G (or whatever, I think that the UML kernel should pass its 
bottom address). At the moment, I'm studying it and the exec-shield patch: 
that patch keeps track of the maximum possible value of EIP for a task and 
sets the code segment limit to that value. This can be applied 
straight-forwardly. But here a malicious software could modify the ?S (CS, 
DS...) registers and point them anywhere inside the LDT and the GDT. So, 
sadly, making this work means reducing the size limit in each valid entry of 
the LDT and the GDT (for the GDT this is about 1 entry, actually); and the 
LDT can be modified by the user through sys_modify_ldt, so we must be 
especially careful there (i.e. restrict the limit the user has told us).

- API:

the UML kernel has to tell the host kernel:

- that the child process must be insulated when it is attached to (or when it 
sends the PTRACE_TRACEME request); a variant of the request which allows 
specifying the bottom address must be introduced (addr and data are ignored, 
so I can't make them meaningful); the names could be PTRACE_ABSTRACTME and 
PTRACE_ABSTRACT (since the child process is "abstracted" from the host). And 
that value has to be saved somewhere (if it is taken in units of at least 
64k, it could be put in the high bytes of task_struct-> ptrace, which avoids 
the need of adding members to task_struct).

- instead of PTRACE_SYSEMU, PTRACE_KERNELEMU, which would do the lazy 
tlb-switching: PTRACE_SYSEMU is IMO valuable enough to stand on its own, even 
if it is no more needed by UML.

Any comments or ideas?
-- 
Paolo Giarrusso, aka Blaisorblade
Linux registered user n. 292729




-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite!  GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[Jeff Dike]

blaisorblade_spam@yahoo.it said:
> Hi Jeff, I would like to ask you to make the current form of the SKAS4
> patch,  even if incomplete, public on the -devel mailing list, even if
> it is not yet  ready;

Yeah, that's something I just haven't got around to doing.

> You said you sometimes feel you have too much work to do; just ask for
> help!  If you want to give some tasks away, just ask for help! 

Thanks to your prodding, I have things set up so that other people can
make official releases of things.  So, if anyone wanted to contribute 
filesystems or binary packages, work on the site, or take over host patches or
the utilities, that is now more workable.

> But just now, I've read on your  diary you planned to have only 1
> process for each UML processor; would that  guarantee 0
> context-switches or not? 

Yes, it would.

> Also, this requires coming back to  having a
> 2,5G TASK_SIZE inside UML, with the upper part for the UML and the
> lower to the host process. Would you accept it?

It might.  With the scheme you outline, it would.  I was also considering
a plan where there would be a memory switch in there as well.  Then, you
replace full process switches with memory switches, which may not be too
much of a win.  Your scheme has problems too, see below.

> In detail (skip this if you got what I mean): to do a syscall, without
> SYSEMU  there is a CS to the guest kernel (which invalidates tons of
> TLBs, i.e. is  the heavier of all ones) + a few instruction + the two
> useless CS's deleted  by SYSEMU, which invalidate a very few TLB
> entries (I think that only 1-2  pages of code + data will have be
> accessed) + the syscall execution (using a  lot of memory) + the final
> context switch to the userspace program, which  will now take a lot of
> time to refill its TLB. 

On x86, which doesn't have tagged TLBs IIRC, there has to be a full tlb
flush no matter how large the processes involved in the switch.  What I'm
not clear on is whether small full flushes are faster than big ones.

> The hard part is the  segmentation protection, since I need to change
> the whole GDT and the whole  LDT!

Yeah.  This is slow, plus using segments will cost you a cycle or something
on every memory reference.  Alan Cox warned me off very strongly against
doing this.  So, you have a tradeoff between a cost taken at system call time
vs a smaller cost plus every memory reference being slower.

> DS points to a struct desc_struct in memory  (which is decoded by the
> CPU) which can say: refuse access to virtual  addresses > 2,5G (or
> whatever, I think that the UML kernel should pass its  bottom
> address). At the moment, I'm studying it and the exec-shield patch:
> that patch keeps track of the maximum possible value of EIP for a task
> and  sets the code segment limit to that value. This can be applied
> straight-forwardly. But here a malicious software could modify the ?S
> (CS,  DS...) registers and point them anywhere inside the LDT and the
> GDT. So,  sadly, making this work means reducing the size limit in
> each valid entry of  the LDT and the GDT (for the GDT this is about 1
> entry, actually); and the  LDT can be modified by the user through
> sys_modify_ldt, so we must be  especially careful there (i.e. restrict
> the limit the user has told us).

Yup, this is what you would do.  Some extra checking in UMLs sys_modify_ldt
would prevent the user from resetting DS.

> Any comments or ideas? 

I would prefer that you look at a full memory switch in PTRACE_SYSEMU rather
than segmentation tricks.  Playing with segments has a variety of 
disadvantages -
	the performance hit on memory references
	the modifying of LDT and GDT, which are slow
	non-portability
	consumption of .5G of process address space
	very limited UML low mem

But in any case, I'm glad you're looking at this.

				Jeff



-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite!  GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[BlaisorBlade]

Alle 06:55, martedì 8 giugno 2004, Jeff Dike ha scritto:

> > But just now, I've read on your  diary you planned to have only 1
> > process for each UML processor; would that  guarantee 0
> > context-switches or not?
>
> Yes, it would.

Hmmm, I meant "would that guarantee 0 memory switches"? And I guess the answer 
to *this* question is "NO".

Yes, actually a Context Switch is different, but I confused them... you say:

> I was also considering a plan where there would be a memory switch
> in there as well
Which is the single-process with memory switches, isn't it?

> > In detail (skip this if you got what I mean): to do a syscall, without
> > SYSEMU  there is a CS to the guest kernel (which invalidates tons of
> > TLBs, i.e. is  the heavier of all ones) + a few instruction + the two
> > useless CS's deleted  by SYSEMU, which invalidate a very few TLB
> > entries (I think that only 1-2  pages of code + data will have be
> > accessed) + the syscall execution (using a  lot of memory) + the final
> > context switch to the userspace program, which  will now take a lot of
> > time to refill its TLB.
>
> On x86, which doesn't have tagged TLBs IIRC, there has to be a full tlb
> flush no matter how large the processes involved in the switch.  What I'm
> not clear on is whether small full flushes are faster than big ones.

I don't think that a flush of fewer TLBs would be faster; what (In My Ignorant 
Opinion) slows things down is not clearing a buffer (it will probably cost 1 
cycle, if they put a RESET pin in the TLBs), but reloading its content when 
memory is read; with SYSEMU, we avoid to reload PTE's for 1-2 host kernel 
pages + the UML kernel pages involved in running the syscall. With this 
approach, instead, we avoid the time for reloading the PTE's for each page in 
the working set of the calling process (which will probably be a much bigger 
win).

> > The hard part is the  segmentation protection, since I need to change
> > the whole GDT and the whole  LDT!
>
> Yeah.  This is slow,

Well, actually it comes to changing 2 segments descriptors (the ones for 
USER_CS and USER_DS) and firewalling sys_modify_ldt which is used almost 
never. Plus the TLS segments, which can be a bit more... but they can be 
"firewalled" too.

> plus using segments will cost you a cycle or something
> on every memory reference.  Alan Cox warned me off very strongly against
> doing this.  So, you have a tradeoff between a cost taken at system call
> time vs a smaller cost plus every memory reference being slower.

Well, using segments here means that the CS and DS descriptor limit are 
lowered, not that I increase base_addr - are you sure that this would have a 
cost? Currently the check is not "disabled" - just the check value is MAX_PTR 
(0xffff....). Yes, the CPUs could be smart enough to optimize the check 
out... I'll try to see if Intel manuals say anything about this.

> > DS points to a struct desc_struct in memory  (which is decoded by the
> > CPU) which can say: refuse access to virtual  addresses > 2,5G (or
> > whatever, I think that the UML kernel should pass its  bottom
> > address). At the moment, I'm studying it and the exec-shield patch:
> > that patch keeps track of the maximum possible value of EIP for a task
> > and  sets the code segment limit to that value. This can be applied
> > straight-forwardly. But here a malicious software could modify the ?S
> > (CS,  DS...) registers and point them anywhere inside the LDT and the
> > GDT. So,  sadly, making this work means reducing the size limit in
> > each valid entry of  the LDT and the GDT (for the GDT this is about 1
> > entry, actually); and the  LDT can be modified by the user through
> > sys_modify_ldt, so we must be  especially careful there (i.e. restrict
> > the limit the user has told us).
>
> Yup, this is what you would do.  Some extra checking in UMLs sys_modify_ldt
> would prevent the user from resetting DS.

Yes, I thought this, too.

> > Any comments or ideas?
>
> I would prefer that you look at a full memory switch in PTRACE_SYSEMU
> rather than segmentation tricks.

> Playing with segments has a variety of
> disadvantages -
> 	the performance hit on memory references

Well, this is the most important one... I'll try to investigate on this.

> 	the modifying of LDT and GDT, which are slow
I hope this is faster than flushing + reloading TLB (by reloading I mean the 
implicit refilling).
> 	non-portability

Well, x86_64 should support this... and anyway each porting would be MUCH 
different in low level details. Yes, since this could be a 3rd mode beyond TT 
and SKAS4 + SYSEMU (joining them will ease a lot porting to other archs... 
SYSEMU is probably easier to implement than the ability to change syscall 
numbers, IMHO), it could be a whole unportable mode, which is not beautiful.

> 	consumption of .5G of process address space
> 	very limited UML low mem
>
> But in any case, I'm glad you're looking at this.

Thanks a lot!
-- 
Paolo Giarrusso, aka Blaisorblade
Linux registered user n. 292729



-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite!  GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[Jeff Dike]

blaisorblade_spam@yahoo.it said:
> I don't think that a flush of fewer TLBs would be faster; what (In My
> Ignorant  Opinion) slows things down is not clearing a buffer (it will
> probably cost 1  cycle, if they put a RESET pin in the TLBs), but
> reloading its content when  memory is read;

> Well, actually it comes to changing 2 segments descriptors (the ones
> for  USER_CS and USER_DS)

> Well, using segments here means that the CS and DS descriptor limit
> are  lowered, not that I increase base_addr - are you sure that this
> would have a  cost? Currently the check is not "disabled" - just the
> check value is MAX_PTR  (0xffff....). Yes, the CPUs could be smart
> enough to optimize the check  out...

You are being way too casual and hard-waving about all this.  I've heard
scary numbers for all of these.

> I'll try to see if Intel manuals say anything about this.

Yes, spend some quality time with the Intel manuals, and see what they say.

> Well, this is the most important one... I'll try to investigate on
> this. 

Actually, the most important factor to me is virtual address space.

				Jeff



-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite!  GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[BlaisorBlade]

Alle 06:55, martedì 8 giugno 2004, Jeff Dike ha scritto:
> blaisorblade_spam@yahoo.it said:

> > In detail (skip this if you got what I mean): to do a syscall, without
> > SYSEMU  there is a CS to the guest kernel (which invalidates tons of
> > TLBs, i.e. is  the heavier of all ones) + a few instruction + the two
> > useless CS's deleted  by SYSEMU, which invalidate a very few TLB
> > entries (I think that only 1-2  pages of code + data will have be
> > accessed) + the syscall execution (using a  lot of memory) + the final
> > context switch to the userspace program, which  will now take a lot of
> > time to refill its TLB.
>
> On x86, which doesn't have tagged TLBs IIRC, there has to be a full tlb
> flush no matter how large the processes involved in the switch.

Sorry, what are tagged TLBs? x86 can flush, on some processors, just some 
TLBs, but for process switch you must flush everything.

Or better, if "tagged TLBs" means that the processor knows with which process 
a TLB is associated, then I understand what you mean and agree with you.

>  What I'm
> not clear on is whether small full flushes are faster than big ones.

Ok, something more definite on this:

http://kerneltrap.org/node/view/2891

the 4G/4G patch creates a situation similar to the current one (without my 
approach) for UML - but they here speak about number-crunching, i.e. only 
about the cost of the interrupt handler, which is ran HZ (= 1000) times per 
second:

"> [*] a nitpick: you keep saying '2000 tlb flushes per second'. This is
>     misleading, there's one flush of the userspace TLBs every 1 msec
>     (i.e. 1000 per second), and one flush of the kernel TLBs - but
>     the kernel TLBs are small at this point, especially with 4MB pages.

I'm saying 2000 tlb flushes only because I'd be wrong saying there are only
1000, but I obviously agree the cost of half of them is not significant (the
footprint of the irq handler is tiny)."

I.e. they (Andrea Arcangeli and Ingo Molnar) agree that the cost of a TLB 
flush changes depending on the number of filled TLBs. And they seem to also 
agree that there is a "secondary cost", the cost of the TLB misses (which is 
IMHO the one which changes depending on how much entries you flush).

See also the benchmark I post (host vs UML with SYSEMU), which show that there 
is an doubling in user time due to executing getpid() vs non executing it, 
while looping over 64 pages (64 pages should mean that the TLB never faults): 
the increase in user time, which is spent mostly by looping onto pages, is 
due to the TLB misses.
-- 
Paolo Giarrusso, aka Blaisorblade
Linux registered user n. 292729




-------------------------------------------------------
This SF.Net email is sponsored by The 2004 JavaOne(SM) Conference
Learn from the experts at JavaOne(SM), Sun's Worldwide Java Developer
Conference, June 28 - July 1 at the Moscone Center in San Francisco, CA
REGISTER AND SAVE! http://java.sun.com/javaone/sf Priority Code NWMGYKND
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

[uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[BlaisorBlade]

Alle 23:05, mercoledì 9 giugno 2004, BlaisorBlade ha scritto:

> > plus using segments will cost you a cycle or something
> > on every memory reference.
The Intel Manual 3 (Intel System Programming Guide - 253668 -15.pdf) says, at 
page 4-1 (page 107 in the PDF), that limit checking has no performance cost, 
and I expect this to hold especially for simply verifying if an address is 
below a limit. Maybe it could lie, ok, but maybe Alan Cox was referring to 
more complex segmentation tricks.

I'm also going to ask to Ingo Molnar (he sets a segment limit in the CS 
descriptor in his exec-shield patch, so he has probably benchmarked the 
result).
-- 
Paolo Giarrusso, aka Blaisorblade
Linux registered user n. 292729




-------------------------------------------------------
This SF.Net email is sponsored by The 2004 JavaOne(SM) Conference
Learn from the experts at JavaOne(SM), Sun's Worldwide Java Developer
Conference, June 28 - July 1 at the Moscone Center in San Francisco, CA
REGISTER AND SAVE! http://java.sun.com/javaone/sf Priority Code NWMGYKND
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] Re: The SKAS4 patch?? + ideas for 0 context-switch

[Jeff Dike]

blaisorblade_spam@yahoo.it said:
> Or better, if "tagged TLBs" means that the processor knows with which
> process  a TLB is associated, then I understand what you mean and
> agree with you. 

Yes.  Tagged TLBs don't require a full flush on a memory switch, and some
process memory context can survive a switch out and back, so the process doesn't
need to start from a context switch with a cold cache.

> I.e. they (Andrea Arcangeli and Ingo Molnar) agree that the cost of a
> TLB  flush changes depending on the number of filled TLBs. And they
> seem to also  agree that there is a "secondary cost", the cost of the
> TLB misses (which is  IMHO the one which changes depending on how much
> entries you flush). 

I didn't really see a clear statement of that in there.  You need to look
at the manuals to be sure.

> The Intel Manual 3 (Intel System Programming Guide - 253668 -15.pdf)
> says, at  page 4-1 (page 107 in the PDF), that limit checking has no
> performance cost,  

I don't see any discussion of performance there.  My copy of the spec dates
from Jan 2002.  Page 107 in the pdf is page 4-3 for me.  Section 4.3 on page
4-4 talks about limit checking, but nothing about performance.

				Jeff



-------------------------------------------------------
This SF.Net email is sponsored by The 2004 JavaOne(SM) Conference
Learn from the experts at JavaOne(SM), Sun's Worldwide Java Developer
Conference, June 28 - July 1 at the Moscone Center in San Francisco, CA
REGISTER AND SAVE! http://java.sun.com/javaone/sf Priority Code NWMGYKND
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel