From: Jeremy Fitzhardinge <hidden> Date: 2007-03-16 20:39:05
David Miller wrote:
Perhaps the problem can be dealt with using ELF relocations.
There is another case, discussed yesterday on netdev, where run-time
resolution of ELF relocations would be useful (for
very-very-very-read-only variables) so if it can solve this problem
too it would be nice to have a generic infrastructure for it.
That's an interesting idea. Have you or anyone else looked at what it
would take to code up?
For this case, I guess you'd walk the relocs looking for references into
the paravirt_ops structure. You'd need to check that was a reference
from an indirect jump or call instruction, which would identify a
patchable callsite. The offset into the pv_ops structure would identify
which operation is involved. That would be enough to use the existing
paravirt_ops patch machinery to insert a patch, though it doesn't
provide quite as much information as the current scheme. The current
scheme also tells us how much space is available for patching over, and
what registers the patched-in code can use/clobber.
What are the netdev requirements?
J
From: Rusty Russell <hidden> Date: 2007-03-18 00:47:34
On Fri, 2007-03-16 at 13:38 -0700, Jeremy Fitzhardinge wrote:
David Miller wrote:
quoted
Perhaps the problem can be dealt with using ELF relocations.
There is another case, discussed yesterday on netdev, where run-time
resolution of ELF relocations would be useful (for
very-very-very-read-only variables) so if it can solve this problem
too it would be nice to have a generic infrastructure for it.
That's an interesting idea. Have you or anyone else looked at what it
would take to code up?
For this case, I guess you'd walk the relocs looking for references into
the paravirt_ops structure. You'd need to check that was a reference
from an indirect jump or call instruction, which would identify a
patchable callsite. The offset into the pv_ops structure would identify
which operation is involved.
I wrote a whole email on ways to do this, BUT...
Perhaps our patching code can already be vastly simplified to something
like:
#define pv_patch(call, args...) \
asm volatile("8888:");
call(args);
asm volatile("8889:"
[ stuff to put 8889, 8888 and call in fixup section ]
The patching code doesn't even need to decode between those two: it
simply looks for an indirect call insn (0xff 0xd?). If it finds more
than one, it doesn't patch. If it only finds one, it patches. We'll
probably hit them all just doing that.
What are the netdev requirements?
Reading Ben LaHaise's (very cool!) patch, it's not clear that using
reloc postprocessing is going to be clearer than open-coding it as he
has done.
Rusty.
From: David Miller <davem@davemloft.net> Date: 2007-03-18 07:33:11
From: Rusty Russell <redacted>
Date: Sat, 17 Mar 2007 21:33:58 +1100
On Fri, 2007-03-16 at 13:38 -0700, Jeremy Fitzhardinge wrote:
quoted
David Miller wrote:
quoted
Perhaps the problem can be dealt with using ELF relocations.
There is another case, discussed yesterday on netdev, where run-time
resolution of ELF relocations would be useful (for
very-very-very-read-only variables) so if it can solve this problem
too it would be nice to have a generic infrastructure for it.
That's an interesting idea. Have you or anyone else looked at what it
would take to code up?
For this case, I guess you'd walk the relocs looking for references into
the paravirt_ops structure. You'd need to check that was a reference
from an indirect jump or call instruction, which would identify a
patchable callsite. The offset into the pv_ops structure would identify
which operation is involved.
I wrote a whole email on ways to do this, BUT...
The idea is _NOT_ that you go look for references to the paravirt_ops
members structure, that would be stupid and you wouldn't be able to
use the most efficient addressing mode on a given cpu, you'd be
patching up indirect calls and crap like that. Just say no...
Instead you get rid of paravirt ops completely, and you call functions
whose symbol name will not resolve in the initial kernel link.
You do an initial link of the kernel, look for the unresolved symbols
in the ELF relocation tables (just like the linker does), and put
those references into a table that is use to patch things up and you
can use standard ELF relocation code to handle this, exactly like code
we already have for module loading in the kernel already.
This idea is about 15 years old, sparc32 has been doing exactly this
via something called "btfixup" to handle the page table, TLB, and
cache differences of 15 different cpu+cache type combinations.
#define pv_patch(call, args...) \
asm volatile("8888:");
call(args);
asm volatile("8889:"
[ stuff to put 8889, 8888 and call in fixup section ]
Please, use ELF and it's powerful and clean existing way to
do this please. :-)
quoted
What are the netdev requirements?
Reading Ben LaHaise's (very cool!) patch, it's not clear that using
reloc postprocessing is going to be clearer than open-coding it as he
has done.
Ben's case can be handled in the same way. Just do not define the
symbols, pre-link, look for the references in the relocation tables,
and run through that when you do the set_very_readonly() or
install_paravirt_ops() thing.
From: Jeremy Fitzhardinge <hidden> Date: 2007-03-18 07:59:07
David Miller wrote:
The idea is _NOT_ that you go look for references to the paravirt_ops
members structure, that would be stupid and you wouldn't be able to
use the most efficient addressing mode on a given cpu, you'd be
patching up indirect calls and crap like that. Just say no...
Instead you get rid of paravirt ops completely, and you call functions
whose symbol name will not resolve in the initial kernel link.
Yeah, I came to that conclusion after thinking about it for a while.
Thanks for the pointer to the sparc stuff; it looks very interesting.
J
The idea is _NOT_ that you go look for references to the paravirt_ops
members structure, that would be stupid and you wouldn't be able to
use the most efficient addressing mode on a given cpu, you'd be
patching up indirect calls and crap like that. Just say no...
That wouldn't handle inlines though. At least some of the current
paravirtops like cli/sti are critical enough to require inlining.
-Andi
From: Jeremy Fitzhardinge <hidden> Date: 2007-03-18 15:58:23
Andi Kleen wrote:
quoted
The idea is _NOT_ that you go look for references to the paravirt_ops
members structure, that would be stupid and you wouldn't be able to
use the most efficient addressing mode on a given cpu, you'd be
patching up indirect calls and crap like that. Just say no...
That wouldn't handle inlines though. At least some of the current
paravirtops like cli/sti are critical enough to require inlining.
You could special-case it in the thing handling the relocs; if you're
relocating to point to a function which you have an inline substitution,
then inline.
The bigger problem is that you don't know what registers you can
clobber. For the pv_ops in hand-written asm, that a big pain. The code
either has to assume the worst, or the "relocator" has to do something
more sophisticated (like look for push/pop pairs surrounding the call,
perhaps?).
J
The bigger problem is that you don't know what registers you can
clobber. For the pv_ops in hand-written asm, that a big pain. The code
either has to assume the worst, or the "relocator" has to do something
more sophisticated (like look for push/pop pairs surrounding the call,
perhaps?).
You could use the dwarf2 unwind tables. They have exact information
what register has what. But it would likely get complicated.
-Andi
On Sun, Mar 18, 2007 at 10:29:10AM -0700, Jeremy Fitzhardinge wrote:
Andi Kleen wrote:
quoted
You could use the dwarf2 unwind tables. They have exact information
what register has what. But it would likely get complicated.
Yes. And would they be accurate for hand-written asm, which is where we
have this problem?
Yes. All inline assembly tells gcc what registers are clobbered
and it fills in the tables. Hand clobbering in inline assembly cannot
be expressed with the current toolchain, so we moved all those
out of line.
But again I'm not sure it will work anyways. For once you would
need large padding around the calls anyways for inline replacement --
how would you generate that? I expect you would need to put the calls
into asm() again and with that a custom annotiation format looks reasonable.
-Andi
From: Jeremy Fitzhardinge <hidden> Date: 2007-03-18 23:46:30
Andi Kleen wrote:
Yes. All inline assembly tells gcc what registers are clobbered
and it fills in the tables. Hand clobbering in inline assembly cannot
be expressed with the current toolchain, so we moved all those
out of line.
But again I'm not sure it will work anyways. For once you would
need large padding around the calls anyways for inline replacement --
how would you generate that? I expect you would need to put the calls
into asm() again and with that a custom annotiation format looks reasonable.
Inlining is most important for very small code: sti, cli, pushf;pop eax,
etc (in many cases, no-ops). We'd have at least 5 bytes to work in, and
maybe more if there are surrounding push/pops to be consumed.
For example, say we wanted to put a general call for sti into entry.S,
where its expected it won't touch any registers. In that case, we'd
have a sequence like:
push %eax
push %ecx
push %edx
call paravirt_cli
pop %edx
pop %ecx
pop %eax
If we parse the relocs, then we'd find the reference to paravirt_cli.
If we look at the byte before and see 0xe8, then we can see if its a
call. If we then work out in each direction and see matched push/pops,
then we know what registers can be trashed in the call. This also
allows us to determine the callsite size, and therefore how much space
we need for inlining.
So in this case, we see that there are 5 bytes for the call and a
further 6 bytes of push/pops available for inlining.
Of course this is hand-written code anyway, so there's no particular
burden to having some extra metadata stashed away in another section.
For compiler-generated code, we know that it's already expecting
standard C ABI calling conventions. The downside, of course, is that
only the 5 byte call space is available for inline patching.
J
On Monday 19 March 2007 00:46, Jeremy Fitzhardinge wrote:
Andi Kleen wrote:
quoted
Yes. All inline assembly tells gcc what registers are clobbered
and it fills in the tables. Hand clobbering in inline assembly cannot
be expressed with the current toolchain, so we moved all those
out of line.
But again I'm not sure it will work anyways. For once you would
need large padding around the calls anyways for inline replacement --
how would you generate that? I expect you would need to put the calls
into asm() again and with that a custom annotiation format looks
reasonable.
Inlining is most important for very small code: sti, cli, pushf;pop eax,
etc (in many cases, no-ops). We'd have at least 5 bytes to work in, and
maybe more if there are surrounding push/pops to be consumed.
For example, say we wanted to put a general call for sti into entry.S,
where its expected it won't touch any registers. In that case, we'd
have a sequence like:
push %eax
push %ecx
push %edx
call paravirt_cli
pop %edx
pop %ecx
pop %eax
This cannot right now be expressed as inline assembly in the unwinder at all
because there is no way to inject the push/pops into the compiler generated
ehframe tables.
[BTW I plan to resubmit the unwinder with some changes]
If we parse the relocs, then we'd find the reference to paravirt_cli.
If we look at the byte before and see 0xe8, then we can see if its a
call. If we then work out in each direction and see matched push/pops,
then we know what registers can be trashed in the call. This also
allows us to determine the callsite size, and therefore how much space
we need for inlining.
gcc normally doesn't generate push/pops around directly around the
call site, but somewhere else due to the way its register allocator works.
It can be anywhere in the function or even not there at all if the register
didn't contain anything useful. And they're not necessarily push/pops of
course.
So you would need to write it as inline assembly. I'm not sure it would
be significantly cleaner than just having tables then.
So in this case, we see that there are 5 bytes for the call and a
further 6 bytes of push/pops available for inlining.
Of course this is hand-written code anyway, so there's no particular
burden to having some extra metadata stashed away in another section.
For compiler-generated code, we know that it's already expecting
standard C ABI calling conventions. The downside, of course, is that
only the 5 byte call space is available for inline patching.
It's unlikely you can do much useful in 5 bytes I guess.
Regarding cli/sti: i've been actually thinking about changing it in the
non paravirt kernel. IIRC most save_flags/restore_flags are inside
spin_lock_irqsave/restore() and that is a separate function anyways
so a little larger special case code is ok as long as it is not slower.
There is some evidence that at least on P4 a software cli/sti flag without
pushf/popf would be faster.
-Andi
From: Jeremy Fitzhardinge <hidden> Date: 2007-03-19 17:58:32
Andi Kleen wrote:
quoted
push %eax
push %ecx
push %edx
call paravirt_cli
pop %edx
pop %ecx
pop %eax
This cannot right now be expressed as inline assembly in the unwinder at all
because there is no way to inject the push/pops into the compiler generated
ehframe tables.
I was thinking more of entry.S rather than inline asms. The only ones I
can think of which would be relevant are the interrupt operations in
spinlocks, and even then we get a bit more leeway.
gcc normally doesn't generate push/pops around directly around the
call site, but somewhere else due to the way its register allocator works.
It can be anywhere in the function or even not there at all if the register
didn't contain anything useful. And they're not necessarily push/pops of
course.
Right, I'm not making any assumptions about what gcc generates for
calls, other than assuming it uses a standard "call X" direct call
instruction.
So you would need to write it as inline assembly. I'm not sure it would
be significantly cleaner than just having tables then.
No, my intention is that the vast majority of pv_ops uses, which are
calls from C code, would simply be normal C calls, syntatically and
semantically.
It's unlikely you can do much useful in 5 bytes I guess.
I think the main value is retaining non-PARAVIRT native performance
levels. In the native case, the inlined instructions amount to 1 or 2
bytes, and having small patch sites is an advantage because there's less
space wasted on nops. My understanding is that a direct call has almost
zero overhead on modern processors, because both the call and the return
can be completely predicted and prefetched, so the threshhold at which
you make inline vs call tradeoff is pretty small.
Regarding cli/sti: i've been actually thinking about changing it in the
non paravirt kernel. IIRC most save_flags/restore_flags are inside
spin_lock_irqsave/restore() and that is a separate function anyways
so a little larger special case code is ok as long as it is not slower.
There is some evidence that at least on P4 a software cli/sti flag without
pushf/popf would be faster.
There are also the ones in entry.S. I suppose spinlocks do get used
more than syscalls and interrupts.
J
On Monday 19 March 2007 00:46, Jeremy Fitzhardinge wrote:
quoted
Andi Kleen wrote:
For example, say we wanted to put a general call for sti into entry.S,
where its expected it won't touch any registers. In that case, we'd
have a sequence like:
push %eax
push %ecx
push %edx
call paravirt_cli
pop %edx
pop %ecx
pop %eax
This cannot right now be expressed as inline assembly in the unwinder at all
because there is no way to inject the push/pops into the compiler generated
ehframe tables.
[BTW I plan to resubmit the unwinder with some changes]
It's inability to handle sequences like the above sounds to me like
a very good argument to _not_ merge the unwinder back into the tree.
To me, that unwinder is nothing but trouble, it severly limits what
cases you can use special calling conventions via inline asm (and we
have done that on several occaisions) and even ignoring that the
unwinder only works half the time.
Please don't subject us to another couple months of hair-pulling only
to have Linus yank the thing out again, there are certainly more
useful things to spend time on :-)
It's inability to handle sequences like the above sounds to me like
a very good argument to _not_ merge the unwinder back into the tree.
The unwinder can handle it fine, it is just that gcc right now cannot
be taught to generate correct unwind tables for it. If paravirt ops
is widely used i guess it would be possible to find some workaround
for that though.
There is one case it truly cannot handle (it would be possible by switching
to dwarf3), but that was relatively easily eliminated and wasn't a problem
imho.
To me, that unwinder is nothing but trouble, it severly limits what
cases you can use special calling conventions via inline asm (and we
have done that on several occaisions) and even ignoring that the
unwinder only works half the time.
Initially we had some bugs that accounted for near all failures, but they
were all fixed in the latest version.
Please don't subject us to another couple months of hair-pulling only
to have Linus yank the thing out again, there are certainly more
useful things to spend time on :-)
I think better backtraces are a good use of my time. Sorry if you
disagree on that.
-Andi
Initially we had some bugs that accounted for near all failures, but they
were all fixed in the latest version.
No. The real bugs were that the people involved wouldn't even accept that
unwinding information was inevitably buggy and/or incomplete.
That much more fundamental bug never got fixed, as far as I know.
I'm not going to merge anything that depends on unwind tables as things
stand. The pain just isn't worth it.
quoted
Please don't subject us to another couple months of hair-pulling only
to have Linus yank the thing out again, there are certainly more
useful things to spend time on :-)
Good call. Dwarf2 unwinding simply isn't worth doing. But I won't yank it
out, I simply won't merge it. It was more than just totally buggy code, it
was an inability of the people to understand that even bugfree code
isn't enough - you have to be able to also handle buggy data.
Linus
Please don't subject us to another couple months of hair-pulling only
to have Linus yank the thing out again, there are certainly more
useful things to spend time on :-)
Good call. Dwarf2 unwinding simply isn't worth doing. But I won't yank it
out, I simply won't merge it. It was more than just totally buggy code, it
was an inability of the people to understand that even bugfree code
isn't enough - you have to be able to also handle buggy data.
For example, say we wanted to put a general call for sti into entry.S,
where its expected it won't touch any registers. In that case, we'd
have a sequence like:
push %eax
push %ecx
push %edx
call paravirt_cli
pop %edx
pop %ecx
pop %eax
If we parse the relocs, then we'd find the reference to paravirt_cli.
If we look at the byte before and see 0xe8, then we can see if its a
call. If we then work out in each direction and see matched push/pops,
then we know what registers can be trashed in the call. This also
allows us to determine the callsite size, and therefore how much space
we need for inlining.
No, that is a very dangerous suggestion. You absolutely *cannot* do
this safely without explicitly marking the start EIP of this code. You
*must* use metadata to do that. It is never safe to disassemble
backwards or "rewind" EIP for x86 code.
Zach
From: Jeremy Fitzhardinge <hidden> Date: 2007-03-20 01:49:54
Zachary Amsden wrote:
Jeremy Fitzhardinge wrote:
quoted
If we then work out in each direction and see matched push/pops,
then we know what registers can be trashed in the call. This also
allows us to determine the callsite size, and therefore how much space
we need for inlining.
No, that is a very dangerous suggestion. You absolutely *cannot* do
this safely without explicitly marking the start EIP of this code.
You *must* use metadata to do that. It is never safe to disassemble
backwards or "rewind" EIP for x86 code.
What do you mean the instruction before is "mov $0x52515000,%eax"?
Yeah, you're right. Oh well.
J
From: Rusty Russell <hidden> Date: 2007-03-19 02:48:21
On Sun, 2007-03-18 at 13:08 +0100, Andi Kleen wrote:
quoted
The idea is _NOT_ that you go look for references to the paravirt_ops
members structure, that would be stupid and you wouldn't be able to
use the most efficient addressing mode on a given cpu, you'd be
patching up indirect calls and crap like that. Just say no...
That wouldn't handle inlines though. At least some of the current
paravirtops like cli/sti are critical enough to require inlining.
Well, we'd patch the inline over the call if we have room.
Magic patching would be neat, but the downsides are that (1) we can't
expand the patching room and (2) there's no way of attaching clobber
info to the call site (doing register liveness analysis is not
appealing).
Now, this may not be fatal. 5 bytes is enough for all the native ops to
be patched inline. For lguest this covers popf and pushf, but not cli
and sti (10 bytes): they'd have to be calls.
As for clobber info, it turns out that almost all of the calls can
clobber %eax, which is probably enough. We just need to mark the
handful of asm ones where this isn't true.
Thoughts?
Rusty.