Skip to contentSkip to conversation

Wanted: simple, safe x86 stack overflow detection

DISCUSSION Chuck Ebbert 10 participants 20 messages Feb 28, 2007 – Mar 19, 2007

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

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...

Quoted 8 lines · Chuck Ebbert

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 2 lines
-
Thiago Galesi
#2 lore raw
In reply to Chuck Ebbert
Quoted 2 lines · Chuck Ebbert

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

#3 lore raw
Quoted 8 lines · Andi Kleen

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.

Quoted 8 lines

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

#4 lore raw
Quoted 3 lines · Bill Irwin

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

Signature · 1 line
ft: http://freshmeat.net/p/chaostables/
#5 lore raw
Quoted 2 lines · Bill Irwin
Quoted 2 lines

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.

Quoted 4 lines · Jan Engelhardt

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

#6 lore raw
In reply to Andi Kleen
Quoted 8 lines · Andi Kleen

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

#18 lore raw
In reply to Chuck Ebbert
Quoted 2 lines · Chuck Ebbert

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 <><
#19 lore raw
Quoted 8 lines · Arnd Bergmann
Quoted 2 lines · Chuck Ebbert

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

#7 lore raw
In reply to Bill Irwin
Quoted 10 lines · Bill Irwin
Quoted 8 lines · Andi Kleen

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.

Quoted 5 lines

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.

#8 lore raw
Quoted 4 lines · Chuck Ebbert

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

#17 lore raw
In reply to Chuck Ebbert
Quoted 1 line · Bill Irwin
Quoted 1 line

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

Quoted 4 lines · Chuck Ebbert

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

#9 lore raw
In reply to Hugh Dickins
Quoted 3 lines · Chuck Ebbert
Quoted 3 lines

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.

Quoted 5 lines · Hugh Dickins

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

#10 lore raw
Quoted 3 lines

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)

#11 lore raw
Quoted 3 lines · At some point in the past, I wrote:
Quoted 3 lines

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.

Quoted 7 lines · Arjan van de Ven

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

#12 lore raw
Quoted 14 lines · Bill Irwin
Quoted 3 lines · At some point in the past, I wrote:
Quoted 3 lines

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.

Quoted 7 lines · Arjan van de Ven

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)

Quoted 1 line

What do you see as the obstacle to eliminating nested IRQ's?

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

Quoted 5 lines

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...

Signature · 2 lines
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
#13 lore raw
Quoted 1 line · Bill Irwin
Quoted 1 line

What do you see as the obstacle to eliminating nested IRQ's?

Quoted 1 line · Arjan van de Ven

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

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

Quoted 5 lines · Bill Irwin
Quoted 5 lines

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?

Quoted 11 lines · Arjan van de Ven

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();
Quoted 1 line

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

#14 lore raw
Quoted 6 lines
Quoted 2 lines

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.

Signature · 2 lines
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
#15 lore raw
In reply to Bill Irwin
Quoted 36 lines · Bill Irwin
Quoted 2 lines · Bill Irwin
Quoted 2 lines

What do you see as the obstacle to eliminating nested IRQ's?

Quoted 2 lines · Arjan van de Ven

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

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

Quoted 6 lines · Bill Irwin
Quoted 6 lines

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?

Quoted 11 lines · Arjan van de Ven

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();
Quoted 7 lines
Quoted 2 lines

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?

Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
#16 lore raw
Quoted 7 lines · Avi Kivity

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