ARM: enable dumping stacks for CONFIG_SMP

Unwinding with CONFIG_ARM_UNWIND is much more complicated than unwinding with CONFIG_FRAME_POINTER, but there are only a few points that require validation in order to avoid faults or infinite loops. Avoiding faults is easy by adding checks to verify that all accesses relative to the frame's stack pointer remain inside the stack.

When CONFIG_FRAME_POINTER is not set it is possible for two frames to have the same SP, so there is no way to avoid repeated calls to unwind_frame continuing forever.

Signed-off-by Colin Cross <[email protected]>

---

Unwinding with CONFIG_ARM_UNWIND is much more complicated than unwinding with CONFIG_FRAME_POINTER, but there are only a few points that require validation in order to avoid faults or infinite loops. Avoiding faults is easy by adding checks to verify that all accesses relative to the frame's stack pointer remain inside the stack.

When CONFIG_FRAME_POINTER is not set it is possible for two frames to have the same SP, so there is no way to avoid repeated calls to unwind_frame continuing forever.

Quoted 6 lines · Colin Cross

Unwinding with CONFIG_ARM_UNWIND is much more complicated than unwinding with CONFIG_FRAME_POINTER, but there are only a few points that require validation in order to avoid faults or infinite loops. Avoiding faults is easy by adding checks to verify that all accesses relative to the frame's stack pointer remain inside the stack.

Quoted 3 lines

When CONFIG_FRAME_POINTER is not set it is possible for two frames to have the same SP, so there is no way to avoid repeated calls to unwind_frame continuing forever.

So here you admit that this patch can cause the unwinder to loop forever, which would provide no way out of that. Why do you think this patch is suitable for mainline with such a problem?

Quoted 7 lines · Russell King - ARM Linux

Quoted 6 lines · Colin Cross

Unwinding with CONFIG_ARM_UNWIND is much more complicated than unwinding with CONFIG_FRAME_POINTER, but there are only a few points that require validation in order to avoid faults or infinite loops. Avoiding faults is easy by adding checks to verify that all accesses relative to the frame's stack pointer remain inside the stack.

Quoted 7 lines

Quoted 3 lines

When CONFIG_FRAME_POINTER is not set it is possible for two frames to have the same SP, so there is no way to avoid repeated calls to unwind_frame continuing forever.

So here you admit that this patch can cause the unwinder to loop forever, which would provide no way out of that. Why do you think this patch is suitable for mainline with such a problem?

With CONFIG_FRAME_POINTER we have a straightforward definition of
progress: the sp must increase per frame, and cannot increase beyond the limit of the tasks stack. We get this property from the fact that each frame record consumes actual space on the stack. If we parse a frame record which does not both increase the sp and provide a frame address greater than that sp, we know that frame is garbage and we must stop.

With CONFIG_ARM_UNWIND, we have no straightforward definition of progress. However, sp must _normally_ still increase, because compiler- generated non-leaf functions must store the lr somewhere, and the compiler always uses the stack. Even if lr is stashed in r4, an ABI compliant would then have needed to save r4 on the stack beforehand.

We can assume that we will never parse a garbage unwind table because of the way the table lookup works (though we may parse a valid table which has nothing whatever to do with the code that was executing in the case of a corrupted stack). So we only need to worry about what the unwind tables will look like for valid functions.

Nonetheless, tail-call-optimised and manually-annotated functions may have unusual frames which don't consume any stack. Stackless tail- call-optimised functions shouldn't be a problem, since their frames are completely missing from the backtrace and won't dump us into a loop. Stackless assembler functions are overwhelmingly likely to be leaf functions, giving us just one stackless frame.

Would it make sense if we place some small sanity limit on the number of frames the unwinder will process with the same sp before giving up?

Quoted 45 lines · Dave Martin

Quoted 7 lines · Russell King - ARM Linux

Quoted 6 lines · Colin Cross

Unwinding with CONFIG_ARM_UNWIND is much more complicated than unwinding with CONFIG_FRAME_POINTER, but there are only a few points that require validation in order to avoid faults or infinite loops. Avoiding faults is easy by adding checks to verify that all accesses relative to the frame's stack pointer remain inside the stack.

Quoted 7 lines

Quoted 3 lines

When CONFIG_FRAME_POINTER is not set it is possible for two frames to have the same SP, so there is no way to avoid repeated calls to unwind_frame continuing forever.

So here you admit that this patch can cause the unwinder to loop forever, which would provide no way out of that. Why do you think this patch is suitable for mainline with such a problem?

With CONFIG_FRAME_POINTER we have a straightforward definition of
progress: the sp must increase per frame, and cannot increase beyond the limit of the tasks stack. We get this property from the fact that each frame record consumes actual space on the stack. If we parse a frame record which does not both increase the sp and provide a frame address greater than that sp, we know that frame is garbage and we must stop.

With CONFIG_ARM_UNWIND, we have no straightforward definition of progress. However, sp must _normally_ still increase, because compiler- generated non-leaf functions must store the lr somewhere, and the compiler always uses the stack. Even if lr is stashed in r4, an ABI compliant would then have needed to save r4 on the stack beforehand.

We can assume that we will never parse a garbage unwind table because of the way the table lookup works (though we may parse a valid table which has nothing whatever to do with the code that was executing in the case of a corrupted stack). So we only need to worry about what the unwind tables will look like for valid functions.

Nonetheless, tail-call-optimised and manually-annotated functions may have unusual frames which don't consume any stack. Stackless tail- call-optimised functions shouldn't be a problem, since their frames are completely missing from the backtrace and won't dump us into a loop. Stackless assembler functions are overwhelmingly likely to be leaf functions, giving us just one stackless frame.

Quoted 2 lines

Would it make sense if we place some small sanity limit on the number of frames the unwinder will process with the same sp before giving up?

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Quoted 11 lines · Colin Cross

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Talking to some tools guys about this, it sounds like there really shouldn't be any stackless frame except for the leaf frame. If there are stackless functions they will probably not be visible in the frame chain at all. So it might make sense to have a pretty small limit. Maybe it could even be 1. Cartainly a small number.

We should also add a check for whether the current and frame and previous frame appear identical and abort if that's the case, if we don't do that already.

Quoted 19 lines · Dave Martin

Quoted 11 lines · Colin Cross

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Talking to some tools guys about this, it sounds like there really shouldn't be any stackless frame except for the leaf frame. If there are stackless functions they will probably not be visible in the frame chain at all. So it might make sense to have a pretty small limit. Maybe it could even be 1. Cartainly a small number.

Quoted 3 lines

We should also add a check for whether the current and frame and previous frame appear identical and abort if that's the case, if we don't do that already.

The case that actually worries me is not the "end up looping for ever" case, but the effects of having the stack change while the unwinder is reading from it - for example:

                /* pop R4-R15 according to mask */
                load_sp = mask & (1 << (13 - 4));
                while (mask) {
                        if (mask & 1)
                                ctrl->vrs[reg] = *vsp++;
                        mask >>= 1;
                        reg++;
                }

Remember that for a running thread, the stack will be changing all the time while another CPU tries to read it to do the unwind, and also remember that the bottom of stack isn't really known. All you have is the snapshot of the registers when the thread was last stopped by the scheduler, and that state probably isn't valid.

So what you're asking is for the unwinder to produce a backtrace from a kernel stack which is possibly changing beneath it from an unknown current state.

This doesn't sound like a particularly bright thing to be doing...

Quoted 37 lines · Russell King - ARM Linux

Quoted 19 lines · Dave Martin

Quoted 11 lines · Colin Cross

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Talking to some tools guys about this, it sounds like there really shouldn't be any stackless frame except for the leaf frame. If there are stackless functions they will probably not be visible in the frame chain at all. So it might make sense to have a pretty small limit. Maybe it could even be 1. Cartainly a small number.

Quoted 3 lines

We should also add a check for whether the current and frame and previous frame appear identical and abort if that's the case, if we don't do that already.

The case that actually worries me is not the "end up looping for ever" case, but the effects of having the stack change while the unwinder is reading from it - for example:

                /* pop R4-R15 according to mask */
                load_sp = mask & (1 << (13 - 4));
                while (mask) {
                        if (mask & 1)
                                ctrl->vrs[reg] = *vsp++;
                        mask >>= 1;
                        reg++;
                }

Quoted 5 lines

Remember that for a running thread, the stack will be changing all the time while another CPU tries to read it to do the unwind, and also remember that the bottom of stack isn't really known. All you have is the snapshot of the registers when the thread was last stopped by the scheduler, and that state probably isn't valid.

So long as the unwinder enforces continuous progress towards a fixed limit, sooner or later the supposed bottom of the stack will be reached, or the unwinder will encounter something which is recognised as garbage and stop.

This the best we can hope for if trying to print a backtrace for a thread without stopping it... which admittedly seems quite a dodgy thing to attempt.

Colin, what are the scenarios when we want to backtrace a thread while it is actually running?

Quoted 5 lines

So what you're asking is for the unwinder to produce a backtrace from a kernel stack which is possibly changing beneath it from an unknown current state.

This doesn't sound like a particularly bright thing to be doing...

Nonetheless, the changes are relevant to normal stack dumping too, since when we take a fault the sp or stack may be corrupted, even if the thread in question is stopped. Being more robust against infinte loops etc., still seems like a good idea ?

Quoted 19 lines · Dave Martin

Quoted 11 lines · Colin Cross

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Talking to some tools guys about this, it sounds like there really shouldn't be any stackless frame except for the leaf frame. If there are stackless functions they will probably not be visible in the frame chain at all. So it might make sense to have a pretty small limit. Maybe it could even be 1. Cartainly a small number.

Quoted 3 lines

We should also add a check for whether the current and frame and previous frame appear identical and abort if that's the case, if we don't do that already.

The case that actually worries me is not the "end up looping for ever" case, but the effects of having the stack change while the unwinder is reading from it - for example:

                /* pop R4-R15 according to mask */
                load_sp = mask & (1 << (13 - 4));
                while (mask) {
                        if (mask & 1)
                                ctrl->vrs[reg] = *vsp++;
                        mask >>= 1;
                        reg++;
                }

Remember that for a running thread, the stack will be changing all the time while another CPU tries to read it to do the unwind, and also remember that the bottom of stack isn't really known. All you have is the snapshot of the registers when the thread was last stopped by the scheduler, and that state probably isn't valid.

So what you're asking is for the unwinder to produce a backtrace from a kernel stack which is possibly changing beneath it from an unknown current state.

This doesn't sound like a particularly bright thing to be doing...

Quoted 37 lines · Russell King - ARM Linux

Quoted 19 lines · Dave Martin

Quoted 11 lines · Colin Cross

About half the callers to unwind_frame end up limiting the number of frames they will follow before giving up, so I wasn't sure if I should put an arbitrary limit in unwind_frame or just make sure all callers are bounded. Your idea of limiting same sp frames instead of total frames sounds better. I can send a new patch that adds a new field to struct stackframe (which will need to be initialized everywhere, the struct is usually on the stack) and limits the recursion. Any suggestion on the recursion limit? I would never expect to see a real situation with more than a few, but on the other hand parsing the frames should be pretty fast so a high number (100?) shouldn't cause any user visible effect.

Talking to some tools guys about this, it sounds like there really shouldn't be any stackless frame except for the leaf frame. If there are stackless functions they will probably not be visible in the frame chain at all. So it might make sense to have a pretty small limit. Maybe it could even be 1. Cartainly a small number.

Quoted 3 lines

We should also add a check for whether the current and frame and previous frame appear identical and abort if that's the case, if we don't do that already.

The case that actually worries me is not the "end up looping for ever" case, but the effects of having the stack change while the unwinder is reading from it - for example:

                /* pop R4-R15 according to mask */
                load_sp = mask & (1 << (13 - 4));
                while (mask) {
                        if (mask & 1)
                                ctrl->vrs[reg] = *vsp++;
                        mask >>= 1;
                        reg++;
                }

Quoted 5 lines

Remember that for a running thread, the stack will be changing all the time while another CPU tries to read it to do the unwind, and also remember that the bottom of stack isn't really known. All you have is the snapshot of the registers when the thread was last stopped by the scheduler, and that state probably isn't valid.

If the snapshot of the registers when the thread was last stopped includes an sp that points somewhere in two contiguous pages of low memory, I don't see a problem. From the sp we can get the bounds of the stack (see the valid_stack_addr function I added), and we can make sure the unwinder never dereferences anything outside of that stack, so it will never fault. We can also make sure that the sp stays within that stack between frames, and moves in the right direction, so it will never loop (except for the leaf-node sp issue, which Dave Martin's idea will address).

Quoted 3 lines

So what you're asking is for the unwinder to produce a backtrace from a kernel stack which is possibly changing beneath it from an unknown current state.

I don't think the stack changing is relevant. With my modifications, the unwinder can handle an invalid value at any place in the stack without looping or crashing, and it doesn't matter if it is invalid due to changing or permanent stack corruption. The worst it will do is produce a partial stack trace that ends with an invalid value. For example:

shell@:/ # dd if=/dev/urandom of=/dev/null bs=1000000 count=1000000 &
[1] 2709
130|shell@:/ # while true; do cat /proc/2709/stack; echo ---; done

[<c00084d4>] gic_handle_irq+0x24/0x58
[<c000e580>] __irq_svc+0x40/0x70

[<ffffffff>] 0xffffffff
---
[<00000099>] 0x99
[<ffffffff>] 0xffffffff
---

[<c0039728>] irq_exit+0x7c/0x98
[<c000f888>] handle_IRQ+0x50/0xac
[<c00084d4>] gic_handle_irq+0x24/0x58

[<00000014>] 0x14
[<ffffffff>] 0xffffffff
---
[<c087ac40>] rcu_preempt_state+0x0/0x140
[<ffffffff>] 0xffffffff
---

[<c00084d4>] gic_handle_irq+0x24/0x58
[<c000e580>] __irq_svc+0x40/0x70

[<ffffffff>] 0xffffffff
---
[<60000013>] 0x60000013
[<ffffffff>] 0xffffffff
---
[<d79ce000>] 0xd79ce000
[<ffffffff>] 0xffffffff

Quoted 1 line

This doesn't sound like a particularly bright thing to be doing...

As discussed previously, this already happens, has anyone ever reported it as a problem? Sysrq-t dumps all stacks by calling dump_backtrace(), which bypasses the check for tsk == current. And any caller to unwind_backtrace with preemption on can see a changing stack, even on UP.

This topic has come up before, see
http://comments.gmane.org/gmane.linux.ports.arm.kernel/102458
for the previous discussion.

SMP is now the norm for new ARM systems, and the limitation that CONFIG_STACKTRACE doesn't work for tasks besides 'current' causes problems. The particular case I'm dealing with is automated debugging information collected from /proc/<pid>/stack when userspace detects a process is not responding.

Dumping stacktraces is currently disabled due to the worry that the task may be running on another CPU and that the unwinder may be unstable when presented with a stack that is being modified. I have attempted to harden the frame pointer based unwinder and the unwind table based unwinder against invalid stacks. I separated the two into individual patches, as I expect the patch to the table unwinder to be more controversial than the frame pointer unwinder.

Even without the hardening, unwinding a stack for a running process is not completely untested. When CONFIG_ARM_UNWIND is enabled, sysrq-t calls unwind_backtrace for all tasks including running ones. In addition, any callers to unwind_frame with preemption enabled, including proc_pid_stack, could see a modified stack even on a UP system (pointed out by Rabin Vincent the last time this topic came up).

 arch/arm/kernel/stacktrace.c |   24 +++++++++++++-----------
 arch/arm/kernel/unwind.c     |   31 +++++++++++++++++++++++++++----
 2 files changed, 40 insertions(+), 15 deletions(-)