Wanted: simple, safe x86 stack overflow detection

Wanted: simple, safe x86 stack overflow detection

[Chuck Ebbert]

Can we just put a canary in the threadinfo and check it on every
task switch? What are the drawbacks?

Re: Wanted: simple, safe x86 stack overflow detection

[Thiago Galesi]

I guess most stack corruptions touch only a small part of the stack.
These kinds of corruptions can only be detected from inside the
program.

Anyway, going beyond the program's stack boundaries  would fault the program.

Checking the threadinfo constantly it'll be (IMHO) mostly useless...

On 2/28/07, Chuck Ebbert <cebbert@redhat.com> wrote:
> Can we just put a canary in the threadinfo and check it on every
> task switch? What are the drawbacks?
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>


-- 
-
Thiago Galesi

Re: Wanted: simple, safe x86 stack overflow detection

[Andi Kleen]

On Wed, Feb 28, 2007 at 09:27:09AM -0500, Chuck Ebbert wrote:
> Can we just put a canary in the threadinfo and check it on every
> task switch? What are the drawbacks?

Likely already too late then -- if critical state is overwritten
you crashed before. Also a lot of stack intensive codes
relatively large unused holes so it might miss the canary completely

Anyways if you want a crash on context switch in the non
hole case you can probably get it by just rearranging thread_info a bit.
e.g. put preempt_count first. Any corruption of that will lead
to schedule complaining.

Don't think it is worth it though.

I suppose one could have a CONFIG_DEBUG_STACK_OVERFLOW that gets
the stacks from vmalloc which would catch any overflow with its
guard pages. This is you would need to change __pa() to handle
that too because there might be still some drivers that do
DMA on stack addresses.  Would be somewhat ugly but doable.

But I have my doubts it is worth it again -- in my experience static
analysis works well enough to trace them down and 
there are not that many anyways.

-Andi

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

On Wed, Feb 28, 2007 at 09:41:44PM +0100, Andi Kleen wrote:
> Likely already too late then -- if critical state is overwritten
> you crashed before. Also a lot of stack intensive codes
> relatively large unused holes so it might miss the canary completely
> Anyways if you want a crash on context switch in the non
> hole case you can probably get it by just rearranging thread_info a bit.
> e.g. put preempt_count first. Any corruption of that will lead
> to schedule complaining.
> Don't think it is worth it though.
> I suppose one could have a CONFIG_DEBUG_STACK_OVERFLOW that gets
> the stacks from vmalloc which would catch any overflow with its
> guard pages. This is you would need to change __pa() to handle
> that too because there might be still some drivers that do
> DMA on stack addresses.  Would be somewhat ugly but doable.
> But I have my doubts it is worth it again -- in my experience static
> analysis works well enough to trace them down and 
> there are not that many anyways.

I don't know about the rest of the world, but halting the system in the
case of memory corruption sounds like an extremely good idea to me.


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Jan Engelhardt]

On Feb 28 2007 15:20, Bill Irwin wrote:
>
>I don't know about the rest of the world, but halting the system in the
>case of memory corruption sounds like an extremely good idea to me.

Just because a rather "unimportant" driver (e.g. parport) might oops
thanks to a now-invalid address after memory corruption, I'd still like
to shutdown the system normally - which should be possible when not
using parport after said corruption.


Jan
-- 
ft: http://freshmeat.net/p/chaostables/

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

On Feb 28 2007 15:20, Bill Irwin wrote:
>> I don't know about the rest of the world, but halting the system in the
>> case of memory corruption sounds like an extremely good idea to me.

On Thu, Mar 01, 2007 at 12:36:47AM +0100, Jan Engelhardt wrote:
> Just because a rather "unimportant" driver (e.g. parport) might oops
> thanks to a now-invalid address after memory corruption, I'd still like
> to shutdown the system normally - which should be possible when not
> using parport after said corruption.

Panic on oops/bug is sysctl-activated as things now stand, so you're
all set.


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

On Wed, Feb 28, 2007 at 09:41:44PM +0100, Andi Kleen wrote:
> I suppose one could have a CONFIG_DEBUG_STACK_OVERFLOW that gets
> the stacks from vmalloc which would catch any overflow with its
> guard pages. This is you would need to change __pa() to handle
> that too because there might be still some drivers that do
> DMA on stack addresses.  Would be somewhat ugly but doable.
> But I have my doubts it is worth it again -- in my experience static
> analysis works well enough to trace them down and 
> there are not that many anyways.

In case anyone wants them, patches against v2.6.21-rc2-116-gbb648a0
for this are available from http://oss.oracle.com/~wli/stack_paranoia/

I only did arch/i386/ as per the Linux tradition, though I could
arrange for other arches easily enough, barring those for which I lack
target platforms. Testbooted on qemu -smp 4 with 64KB vmalloc()'d
stacks and IRQ stacks, compiletested in a couple of other configs.
Translation: very light testing. For me this was about reestablishing
reconnoiter of current mainline and familiarizing myself with qemu.

The patch series goes something like:
$ quilt series | xargs -i grep -nH '^Subj' patches/\{\} | cut -f2 -d/ |
cut -f 4 -d: | cat -n
     1   make stack size configurable
     2   add config option to vmalloc stacks
     3   make IRQ stacks independently configurable
     4   go BUG on vmallocspace in __pa()
     5   dynamically allocate IRQ stacks
     6   arrange for a guard page on cpu 0's IRQ stack

Chuck, is any of this of any use to you?


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Arnd Bergmann]

On Wednesday 28 February 2007, Chuck Ebbert wrote:
> Can we just put a canary in the threadinfo and check it on every
> task switch? What are the drawbacks?

It's not completely reliable, in case of functions that allocate
far too much stack space. You might want to take a look at the
gcc support that Andreas Krebbel implemented for s390 to check
for stack overflows:

http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01308.html

I think there are some additions planned for the next gcc release,
but if you port this to i386, it will get you pretty far.

	Arnd <><

Re: Wanted: simple, safe x86 stack overflow detection

[Andi Kleen]

On Mon, Mar 05, 2007 at 02:18:24AM +0100, Arnd Bergmann wrote:
> On Wednesday 28 February 2007, Chuck Ebbert wrote:
> > Can we just put a canary in the threadinfo and check it on every
> > task switch? What are the drawbacks?
> 
> It's not completely reliable, in case of functions that allocate
> far too much stack space. You might want to take a look at the
> gcc support that Andreas Krebbel implemented for s390 to check
> for stack overflows:

I hacked this up for x86-64 too at some point (using 
the gprof support). However it's quite slow.

Here's the old 2.4 patch:

ftp://ftp.x86-64.org/pub/linux/debug/stackcheck-1

-Andi

Re: Wanted: simple, safe x86 stack overflow detection

[Chuck Ebbert]

Bill Irwin wrote:
> On Wed, Feb 28, 2007 at 09:41:44PM +0100, Andi Kleen wrote:
>> I suppose one could have a CONFIG_DEBUG_STACK_OVERFLOW that gets
>> the stacks from vmalloc which would catch any overflow with its
>> guard pages. This is you would need to change __pa() to handle
>> that too because there might be still some drivers that do
>> DMA on stack addresses.  Would be somewhat ugly but doable.
>> But I have my doubts it is worth it again -- in my experience static
>> analysis works well enough to trace them down and 
>> there are not that many anyways.
> 
> In case anyone wants them, patches against v2.6.21-rc2-116-gbb648a0
> for this are available from http://oss.oracle.com/~wli/stack_paranoia/


> Chuck, is any of this of any use to you?


I said "simple." :)

In the 4k/4k stack i386 kernel, is there any fundamental reason it
can't be 4k/8k? We seem to be mostly hitting problems in overflowing
the IRQ stack... I think. Overhead would only be 4k per CPU for that.

Re: Wanted: simple, safe x86 stack overflow detection

[Hugh Dickins]

On Tue, 6 Mar 2007, Chuck Ebbert wrote:
> 
> In the 4k/4k stack i386 kernel, is there any fundamental reason it
> can't be 4k/8k? We seem to be mostly hitting problems in overflowing
> the IRQ stack... I think. Overhead would only be 4k per CPU for that.

For all of history prior to 2.6.20, there's been the fundamental
reason that even interrupt stacks need to access current_thread_info,
and that involved the (THREAD_SIZE - 1) mask.  But 2.6.20's read_pda
using %gs gets away from that: my guess is that it's now possible
for i386 to use different sized stacks.

Hugh

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

Bill Irwin wrote:
>> Chuck, is any of this of any use to you?

On Tue, Mar 06, 2007 at 01:59:39PM -0500, Chuck Ebbert wrote:
> I said "simple." :)
> In the 4k/4k stack i386 kernel, is there any fundamental reason it
> can't be 4k/8k? We seem to be mostly hitting problems in overflowing
> the IRQ stack... I think. Overhead would only be 4k per CPU for that.

current is derived from current_thread_info()->task which is in turn
derived from the stack pointer. Using segmentation to derive per-thread
state would allow i386 to make IRQ and task stack-sizes independent.
There are beginnings of this in the i386 PDA code.

A patch to allow 8K/8K is relatively simple and may serve your
purposes. vmalloc() of the task and IRQ stacks has negative
performance and resource scalability implications, though it's not
particularly involved. It also ensures no memory corruption can occur
from stack overflow save in the case of stack frames larger than a
page, where furthermore the procedure references distant locations
prior to close ones, such as a reverse array walk. Allowing larger
stacksizes than 8K doesn't seem to be of interest to you, probably due
to the negative resource scalability implications, though it may
stabilize some workloads.

I'm not sure what to say on the simplicity front apart from patches
consisting largely of Kconfig edits are demonstrably simple. There
really wasn't much to any of this from my POV, but I do understand
that others may differ particularly on the stack vmalloc() front.
The individual patches of the series are mostly independent save for
textual affairs, and I intended for users to cherrypick whatever
strategies they preferred as per the config options provided. An
individual patch for the preferred strategy can also be respun in
isolation, if any of those provided are considered desirable.

Otherwise I suppose I can actually make use of the PDA to make the
IRQ stacksize independent of the task stacksize.


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

On Tue, 6 Mar 2007, Chuck Ebbert wrote:
>> In the 4k/4k stack i386 kernel, is there any fundamental reason it
>> can't be 4k/8k? We seem to be mostly hitting problems in overflowing
>> the IRQ stack... I think. Overhead would only be 4k per CPU for that.

On Tue, Mar 06, 2007 at 07:43:41PM +0000, Hugh Dickins wrote:
> For all of history prior to 2.6.20, there's been the fundamental
> reason that even interrupt stacks need to access current_thread_info,
> and that involved the (THREAD_SIZE - 1) mask.  But 2.6.20's read_pda
> using %gs gets away from that: my guess is that it's now possible
> for i386 to use different sized stacks.

It's unclear to me how the PDA code differs from the methods of elder
kernels apart from the observation that newer cpu revisions have better
performance in/around segmentation relative to arithmetic operations on
%esp. I'm certainly in favor of the move; IRQ stacks could be made
rather deep and cheaply at that. I may get around to writing it this
week if no one else does it first.


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Arjan van de Ven]

> I'm certainly in favor of the move; IRQ stacks could be made
> rather deep and cheaply at that. I may get around to writing it this
> week if no one else does it first.

the irq stacks aren't the problem; RH at some point accidentally shipped
a kernel with 4k *shared* irq/user context stack and even that gave
almost no issues.

irq's really shouldn't actually nest; it's bad for just about everything
to do that (but that's another story, I would *love* to get rid of the
"enable irqs" thing in the x86 irq path, it hurts just about anything in
reality)

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

At some point in the past, I wrote:
>> I'm certainly in favor of the move; IRQ stacks could be made
>> rather deep and cheaply at that. I may get around to writing it this
>> week if no one else does it first.

On Tue, Mar 06, 2007 at 08:28:35PM -0800, Arjan van de Ven wrote:
> the irq stacks aren't the problem; RH at some point accidentally shipped
> a kernel with 4k *shared* irq/user context stack and even that gave
> almost no issues.
> irq's really shouldn't actually nest; it's bad for just about everything
> to do that (but that's another story, I would *love* to get rid of the
> "enable irqs" thing in the x86 irq path, it hurts just about anything in
> reality)

What do you see as the obstacle to eliminating nested IRQ's? It doesn't
seem so far out to test for being on the interrupt stack and defer the
call to do_IRQ() until after the currently-running instance of do_IRQ()
has returned, or to move to per-irq stacks modulo special arrangements
for the per-cpu IRQ's. Or did you have other methods in mind?


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Arjan van de Ven]

On Tue, 2007-03-06 at 22:44 -0800, Bill Irwin wrote:
> At some point in the past, I wrote:
> >> I'm certainly in favor of the move; IRQ stacks could be made
> >> rather deep and cheaply at that. I may get around to writing it this
> >> week if no one else does it first.
> 
> On Tue, Mar 06, 2007 at 08:28:35PM -0800, Arjan van de Ven wrote:
> > the irq stacks aren't the problem; RH at some point accidentally shipped
> > a kernel with 4k *shared* irq/user context stack and even that gave
> > almost no issues.
> > irq's really shouldn't actually nest; it's bad for just about everything
> > to do that (but that's another story, I would *love* to get rid of the
> > "enable irqs" thing in the x86 irq path, it hurts just about anything in
> > reality)
> 
> What do you see as the obstacle to eliminating nested IRQ's?

political will, or maybe just the lack of convincing people so far

>  It doesn't
> seem so far out to test for being on the interrupt stack and defer the
> call to do_IRQ() until after the currently-running instance of do_IRQ()
> has returned, or to move to per-irq stacks modulo special arrangements
> for the per-cpu IRQ's. Or did you have other methods in mind?

it's simpler...

irqreturn_t handle_IRQ_event(unsigned int irq, struct irqaction *action)
{ 
        irqreturn_t ret, retval = IRQ_NONE;
        unsigned int status = 0;

        handle_dynamic_tick(action);
   
        if (!(action->flags & IRQF_DISABLED))
                local_irq_enable_in_hardirq();


just removing the if() and the explicit IRQ enabling already makes irqs no longer nest...

-- 
if you want to mail me at work (you don't), use arjan (at) linux.intel.com
Test the interaction between Linux and your BIOS via http://www.linuxfirmwarekit.org

Re: Wanted: simple, safe x86 stack overflow detection

[Bill Irwin]

On Tue, 2007-03-06 at 22:44 -0800, Bill Irwin wrote:
>> What do you see as the obstacle to eliminating nested IRQ's?

On Wed, Mar 07, 2007 at 04:34:52AM -0800, Arjan van de Ven wrote:
> political will, or maybe just the lack of convincing people so far

Political issues are significantly more difficult to resolve than
technical ones.


On Tue, 2007-03-06 at 22:44 -0800, Bill Irwin wrote:
>>  It doesn't
>> seem so far out to test for being on the interrupt stack and defer the
>> call to do_IRQ() until after the currently-running instance of do_IRQ()
>> has returned, or to move to per-irq stacks modulo special arrangements
>> for the per-cpu IRQ's. Or did you have other methods in mind?

On Wed, Mar 07, 2007 at 04:34:52AM -0800, Arjan van de Ven wrote:
> it's simpler...
> irqreturn_t handle_IRQ_event(unsigned int irq, struct irqaction *action)
> { 
>         irqreturn_t ret, retval = IRQ_NONE;
>         unsigned int status = 0;
> 
>         handle_dynamic_tick(action);
>    
>         if (!(action->flags & IRQF_DISABLED))
>                 local_irq_enable_in_hardirq();
> 
> just removing the if() and the explicit IRQ enabling already makes irqs no longer nest...

I can see why that would raise eyebrows. I can see getting bashed
mercilessly with interrupt latency concerns as a result here. Can you
suggest any defenses?


-- wli

Re: Wanted: simple, safe x86 stack overflow detection

[Arjan van de Ven]

> > just removing the if() and the explicit IRQ enabling already makes irqs no longer nest...
> 
> I can see why that would raise eyebrows. I can see getting bashed
> mercilessly with interrupt latency concerns as a result here. Can you
> suggest any defenses?


hardirq handlers are supposed to be fast. If they're slow the code
should (and generally is) using bottom halves/tasklets/softirqs. Combine
this with the fact that each new irq handler will start with a bunch of
cache misses, the latency added isn't generally that significant. In
addition, the cache miss thing makes the nesting suck a lot, it's faster
to batch the irqs in sequence.

-- 
if you want to mail me at work (you don't), use arjan (at) linux.intel.com
Test the interaction between Linux and your BIOS via http://www.linuxfirmwarekit.org

Re: Wanted: simple, safe x86 stack overflow detection

[Avi Kivity]

Bill Irwin wrote:
> On Tue, 2007-03-06 at 22:44 -0800, Bill Irwin wrote:
>   
>>> What do you see as the obstacle to eliminating nested IRQ's?
>>>       
>
> On Wed, Mar 07, 2007 at 04:34:52AM -0800, Arjan van de Ven wrote:
>   
>> political will, or maybe just the lack of convincing people so far
>>     
>
> Political issues are significantly more difficult to resolve than
> technical ones.
>
>
> On Tue, 2007-03-06 at 22:44 -0800, Bill Irwin wrote:
>   
>>>  It doesn't
>>> seem so far out to test for being on the interrupt stack and defer the
>>> call to do_IRQ() until after the currently-running instance of do_IRQ()
>>> has returned, or to move to per-irq stacks modulo special arrangements
>>> for the per-cpu IRQ's. Or did you have other methods in mind?
>>>       
>
> On Wed, Mar 07, 2007 at 04:34:52AM -0800, Arjan van de Ven wrote:
>   
>> it's simpler...
>> irqreturn_t handle_IRQ_event(unsigned int irq, struct irqaction *action)
>> { 
>>         irqreturn_t ret, retval = IRQ_NONE;
>>         unsigned int status = 0;
>>
>>         handle_dynamic_tick(action);
>>    
>>         if (!(action->flags & IRQF_DISABLED))
>>                 local_irq_enable_in_hardirq();
>>
>> just removing the if() and the explicit IRQ enabling already makes irqs no longer nest...
>>     
>
> I can see why that would raise eyebrows. I can see getting bashed
> mercilessly with interrupt latency concerns as a result here. Can you
> suggest any defenses?
>   

I don't understand why interrupt latency suffers.  Sure, the interrupt 
that's being masked is delayed, but on the other hand the interrupt 
that's doing the masking is not.  We're moving the latency from the 
first interrupt to the second, probably with a slight gain in overall 
throughput.

It *does* matter if the interrupts have meaningful priorities.  Is that 
the case here?

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: Wanted: simple, safe x86 stack overflow detection

[Eric W. Biederman]

Avi Kivity <avi@argo.co.il> writes:

> I don't understand why interrupt latency suffers.  Sure, the interrupt that's
> being masked is delayed, but on the other hand the interrupt that's doing the
> masking is not.  We're moving the latency from the first interrupt to the
> second, probably with a slight gain in overall throughput.
>
> It *does* matter if the interrupts have meaningful priorities.  Is that the case
> here?

No.

I'll queue this in my irq things to think about...

Eric