[PATCH V4] ARM : unwinder : Prevent data abort due to stack overflow

[PATCH V4] ARM : unwinder : Prevent data abort due to stack overflow

[Anurag Aggarwal]

While unwinding backtrace, stack overflow is possible. This stack
overflow can sometimes lead to data abort in system if the area after
stack is not mapped to physical memory.

To prevent this problem from happening, execute the instructions that
can cause a data abort in separate helper functions, where a check for
feasibility is made before reading each word from the stack.

Signed-off-by: Anurag Aggarwal <a.anurag@samsung.com>
---
 arch/arm/kernel/unwind.c |  127 ++++++++++++++++++++++++++++++++-------------
 1 files changed, 90 insertions(+), 37 deletions(-)

diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
index 00df012..94f6ef4 100644
--- a/arch/arm/kernel/unwind.c
+++ b/arch/arm/kernel/unwind.c
@@ -68,6 +68,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
 struct unwind_ctrl_block {
 	unsigned long vrs[16];		/* virtual register set */
 	const unsigned long *insn;	/* pointer to the current instructions word */
+	unsigned long sp_high;		/* highest value of sp allowed*/
 	int entries;			/* number of entries left to interpret */
 	int byte;			/* current byte number in the instructions word */
 };
@@ -235,6 +236,86 @@ static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
 	return ret;
 }
 
+/* Before poping a register check whether it is feasible or not */
+static int unwind_pop_register(struct unwind_ctrl_block *ctrl,
+				unsigned long **vsp, unsigned int reg)
+{
+	if (*vsp >= (unsigned long *)ctrl->sp_high)
+		return -URC_FAILURE;
+
+	ctrl->vrs[reg] = *(*vsp)++;
+	return URC_OK;
+}
+
+/* Helper functions to execute the instructions */
+static int unwind_exec_pop_subset_r4_to_r13(struct unwind_ctrl_block *ctrl,
+						unsigned long mask)
+{
+	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+	int load_sp, reg = 4;
+
+	load_sp = mask & (1 << (13 - 4));
+	while (mask) {
+		if (mask & 1)
+			if (unwind_pop_register(ctrl, &vsp, reg))
+				return -URC_FAILURE;
+		mask >>= 1;
+		reg++;
+	}
+	if (!load_sp)
+		ctrl->vrs[SP] = (unsigned long)vsp;
+
+	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
+		ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
+
+	return URC_OK;
+}
+
+static int unwind_exec_pop_r4_to_rN(struct unwind_ctrl_block *ctrl,
+					unsigned long insn)
+{
+	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+	int reg;
+
+	/* pop R4-R[4+bbb] */
+	for (reg = 4; reg <= 4 + (insn & 7); reg++)
+		if (unwind_pop_register(ctrl, &vsp, reg))
+				return -URC_FAILURE;
+
+	if (insn & 0x80)
+		if (unwind_pop_register(ctrl, &vsp, 14))
+				return -URC_FAILURE;
+
+	ctrl->vrs[SP] = (unsigned long)vsp;
+
+	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
+		ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
+
+	return URC_OK;
+}
+
+static int unwind_exec_pop_subset_r0_to_r3(struct unwind_ctrl_block *ctrl,
+						unsigned long mask)
+{
+	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
+	int reg = 0;
+
+	/* pop R0-R3 according to mask */
+	while (mask) {
+		if (mask & 1)
+			if (unwind_pop_register(ctrl, &vsp, reg))
+				return -URC_FAILURE;
+		mask >>= 1;
+		reg++;
+	}
+	ctrl->vrs[SP] = (unsigned long)vsp;
+
+	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
+		ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
+
+	return URC_OK;
+}
+
 /*
  * Execute the current unwind instruction.
  */
@@ -250,8 +331,6 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 		ctrl->vrs[SP] -= ((insn & 0x3f) << 2) + 4;
 	else if ((insn & 0xf0) == 0x80) {
 		unsigned long mask;
-		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
-		int load_sp, reg = 4;
 
 		insn = (insn << 8) | unwind_get_byte(ctrl);
 		mask = insn & 0x0fff;
@@ -261,38 +340,19 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 			return -URC_FAILURE;
 		}
 
-		/* pop R4-R15 according to mask */
-		load_sp = mask & (1 << (13 - 4));
-		while (mask) {
-			if (mask & 1)
-				ctrl->vrs[reg] = *vsp++;
-			mask >>= 1;
-			reg++;
-		}
-		if (!load_sp)
-			ctrl->vrs[SP] = (unsigned long)vsp;
+		return unwind_exec_pop_subset_r4_to_r13(ctrl, mask);
 	} else if ((insn & 0xf0) == 0x90 &&
 		   (insn & 0x0d) != 0x0d)
 		ctrl->vrs[SP] = ctrl->vrs[insn & 0x0f];
-	else if ((insn & 0xf0) == 0xa0) {
-		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
-		int reg;
-
-		/* pop R4-R[4+bbb] */
-		for (reg = 4; reg <= 4 + (insn & 7); reg++)
-			ctrl->vrs[reg] = *vsp++;
-		if (insn & 0x80)
-			ctrl->vrs[14] = *vsp++;
-		ctrl->vrs[SP] = (unsigned long)vsp;
-	} else if (insn == 0xb0) {
+	else if ((insn & 0xf0) == 0xa0)
+		return unwind_exec_pop_r4_to_rN(ctrl, insn);
+	else if (insn == 0xb0) {
 		if (ctrl->vrs[PC] == 0)
 			ctrl->vrs[PC] = ctrl->vrs[LR];
 		/* no further processing */
 		ctrl->entries = 0;
 	} else if (insn == 0xb1) {
 		unsigned long mask = unwind_get_byte(ctrl);
-		unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
-		int reg = 0;
 
 		if (mask == 0 || mask & 0xf0) {
 			pr_warning("unwind: Spare encoding %04lx\n",
@@ -300,14 +360,7 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
 			return -URC_FAILURE;
 		}
 
-		/* pop R0-R3 according to mask */
-		while (mask) {
-			if (mask & 1)
-				ctrl->vrs[reg] = *vsp++;
-			mask >>= 1;
-			reg++;
-		}
-		ctrl->vrs[SP] = (unsigned long)vsp;
+		return unwind_exec_pop_subset_r0_to_r3(ctrl, mask);
 	} else if (insn == 0xb2) {
 		unsigned long uleb128 = unwind_get_byte(ctrl);
 
@@ -329,13 +382,13 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
  */
 int unwind_frame(struct stackframe *frame)
 {
-	unsigned long high, low;
+	unsigned long low;
 	const struct unwind_idx *idx;
 	struct unwind_ctrl_block ctrl;
 
-	/* only go to a higher address on the stack */
+	/* store the highest address on the stack to avoid crossing it*/
 	low = frame->sp;
-	high = ALIGN(low, THREAD_SIZE);
+	ctrl.sp_high = ALIGN(low, THREAD_SIZE);
 
 	pr_debug("%s(pc = %08lx lr = %08lx sp = %08lx)\n", __func__,
 		 frame->pc, frame->lr, frame->sp);
@@ -386,7 +439,7 @@ int unwind_frame(struct stackframe *frame)
 		int urc = unwind_exec_insn(&ctrl);
 		if (urc < 0)
 			return urc;
-		if (ctrl.vrs[SP] < low || ctrl.vrs[SP] >= high)
+		if (ctrl.vrs[SP] < low || ctrl.vrs[SP] >= ctrl.sp_high)
 			return -URC_FAILURE;
 	}
 
-- 
1.7.0.4

Re: [PATCH V4] ARM : unwinder : Prevent data abort due to stack overflow

[Dave Martin]

On Thu, Dec 05, 2013 at 11:26:25AM +0000, Anurag Aggarwal wrote:
> While unwinding backtrace, stack overflow is possible. This stack
> overflow can sometimes lead to data abort in system if the area after
> stack is not mapped to physical memory.
> 
> To prevent this problem from happening, execute the instructions that
> can cause a data abort in separate helper functions, where a check for
> feasibility is made before reading each word from the stack.
> 
> Signed-off-by: Anurag Aggarwal <a.anurag@samsung.com>
> ---
>  arch/arm/kernel/unwind.c |  127 ++++++++++++++++++++++++++++++++-------------
>  1 files changed, 90 insertions(+), 37 deletions(-)
> 
> diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
> index 00df012..94f6ef4 100644
> --- a/arch/arm/kernel/unwind.c
> +++ b/arch/arm/kernel/unwind.c
> @@ -68,6 +68,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
>  struct unwind_ctrl_block {
>  	unsigned long vrs[16];		/* virtual register set */
>  	const unsigned long *insn;	/* pointer to the current instructions word */
> +	unsigned long sp_high;		/* highest value of sp allowed*/
>  	int entries;			/* number of entries left to interpret */
>  	int byte;			/* current byte number in the instructions word */
>  };
> @@ -235,6 +236,86 @@ static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
>  	return ret;
>  }
>  
> +/* Before poping a register check whether it is feasible or not */
> +static int unwind_pop_register(struct unwind_ctrl_block *ctrl,
> +				unsigned long **vsp, unsigned int reg)
> +{
> +	if (*vsp >= (unsigned long *)ctrl->sp_high)
> +		return -URC_FAILURE;
> +
> +	ctrl->vrs[reg] = *(*vsp)++;
> +	return URC_OK;

It occurred to me that your optimisation can still be implemented on
top on this.

If you add an extra flag parameter to unwind_pop_register telling it
whether to do checking or not, I think that the compiler and/or
CPU branch predictor should be able to do a pretty good job of
optimising the common case.  Until we get near sp_high, if(check) will
branch the same way every time.

if (unlikely(check) &&
    *vsp >= (unsigned long *)ctrl->sp_high)) 

would make sense, in fact.


I think this brings most of the benefit, without needing to code the
insn exec rules twice.

I'm still not sure the optimisation benefits us much, but I think
that would be a tidier way of doing it if you want to try.

> +}
> +
> +/* Helper functions to execute the instructions */
> +static int unwind_exec_pop_subset_r4_to_r13(struct unwind_ctrl_block *ctrl,
> +						unsigned long mask)
> +{
> +	unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
> +	int load_sp, reg = 4;
> +
> +	load_sp = mask & (1 << (13 - 4));
> +	while (mask) {
> +		if (mask & 1)
> +			if (unwind_pop_register(ctrl, &vsp, reg))
> +				return -URC_FAILURE;
> +		mask >>= 1;
> +		reg++;
> +	}
> +	if (!load_sp)
> +		ctrl->vrs[SP] = (unsigned long)vsp;
> +
> +	pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
> +		ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);

Minor-ish nit: you now duplicate this same pr_debug() in many places.
Apologies, I didn't spot that in the previous review.

What about something like this:

static int unwind_exec_insn(...)
{
	int ret = URC_OK;

	} else if (...)
		ret = unwind_exec_pop_subset_r4_to_r13(...);
		if (ret)
			goto error;
	else ...

	pr_debug(...);

error:
	return ret;
}

Then everything returns through the same pr_debug() after the insn has
been executed.

[...]

> @@ -329,13 +382,13 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
>   */
>  int unwind_frame(struct stackframe *frame)
>  {
> -	unsigned long high, low;
> +	unsigned long low;
>  	const struct unwind_idx *idx;
>  	struct unwind_ctrl_block ctrl;
>  
> -	/* only go to a higher address on the stack */
> +	/* store the highest address on the stack to avoid crossing it*/
>  	low = frame->sp;
> -	high = ALIGN(low, THREAD_SIZE);
> +	ctrl.sp_high = ALIGN(low, THREAD_SIZE);

Does the code check anywhere that SP is word-aligned?

That should probably be checked if it's not done already.

I have some unrelated changes I want to make in this file (which is
part of why I'm being pushy about getting things nice and clean) ... so
I'm happy to follow up with that as a separate patch later.  It's a
separate issue, really.  It doesn't necessarily belong in this patch.

Cheers
---Dave

Re: [PATCH V4] ARM : unwinder : Prevent data abort due to stack overflow

[Anurag Aggarwal]

>>if (unlikely(check) &&
>>    *vsp >= (unsigned long *)ctrl->sp_high))

Good idea, It can help in optimizing the code and will leave code more readable
and it will be easy to maintain also.

>>Does the code check anywhere that SP is word-aligned?
>>
>>That should probably be checked if it's not done already.

I think this should be handled in separate patch
I would also like to hear more your ideas for the file

Regards
Anurag

On Thu, Dec 5, 2013 at 7:29 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> On Thu, Dec 05, 2013 at 11:26:25AM +0000, Anurag Aggarwal wrote:
>> While unwinding backtrace, stack overflow is possible. This stack
>> overflow can sometimes lead to data abort in system if the area after
>> stack is not mapped to physical memory.
>>
>> To prevent this problem from happening, execute the instructions that
>> can cause a data abort in separate helper functions, where a check for
>> feasibility is made before reading each word from the stack.
>>
>> Signed-off-by: Anurag Aggarwal <a.anurag@samsung.com>
>> ---
>>  arch/arm/kernel/unwind.c |  127 ++++++++++++++++++++++++++++++++-------------
>>  1 files changed, 90 insertions(+), 37 deletions(-)
>>
>> diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
>> index 00df012..94f6ef4 100644
>> --- a/arch/arm/kernel/unwind.c
>> +++ b/arch/arm/kernel/unwind.c
>> @@ -68,6 +68,7 @@ EXPORT_SYMBOL(__aeabi_unwind_cpp_pr2);
>>  struct unwind_ctrl_block {
>>       unsigned long vrs[16];          /* virtual register set */
>>       const unsigned long *insn;      /* pointer to the current instructions word */
>> +     unsigned long sp_high;          /* highest value of sp allowed*/
>>       int entries;                    /* number of entries left to interpret */
>>       int byte;                       /* current byte number in the instructions word */
>>  };
>> @@ -235,6 +236,86 @@ static unsigned long unwind_get_byte(struct unwind_ctrl_block *ctrl)
>>       return ret;
>>  }
>>
>> +/* Before poping a register check whether it is feasible or not */
>> +static int unwind_pop_register(struct unwind_ctrl_block *ctrl,
>> +                             unsigned long **vsp, unsigned int reg)
>> +{
>> +     if (*vsp >= (unsigned long *)ctrl->sp_high)
>> +             return -URC_FAILURE;
>> +
>> +     ctrl->vrs[reg] = *(*vsp)++;
>> +     return URC_OK;
>
> It occurred to me that your optimisation can still be implemented on
> top on this.
>
> If you add an extra flag parameter to unwind_pop_register telling it
> whether to do checking or not, I think that the compiler and/or
> CPU branch predictor should be able to do a pretty good job of
> optimising the common case.  Until we get near sp_high, if(check) will
> branch the same way every time.
>
> if (unlikely(check) &&
>     *vsp >= (unsigned long *)ctrl->sp_high))
>
> would make sense, in fact.
>
>
> I think this brings most of the benefit, without needing to code the
> insn exec rules twice.
>
> I'm still not sure the optimisation benefits us much, but I think
> that would be a tidier way of doing it if you want to try.
>
>> +}
>> +
>> +/* Helper functions to execute the instructions */
>> +static int unwind_exec_pop_subset_r4_to_r13(struct unwind_ctrl_block *ctrl,
>> +                                             unsigned long mask)
>> +{
>> +     unsigned long *vsp = (unsigned long *)ctrl->vrs[SP];
>> +     int load_sp, reg = 4;
>> +
>> +     load_sp = mask & (1 << (13 - 4));
>> +     while (mask) {
>> +             if (mask & 1)
>> +                     if (unwind_pop_register(ctrl, &vsp, reg))
>> +                             return -URC_FAILURE;
>> +             mask >>= 1;
>> +             reg++;
>> +     }
>> +     if (!load_sp)
>> +             ctrl->vrs[SP] = (unsigned long)vsp;
>> +
>> +     pr_debug("%s: fp = %08lx sp = %08lx lr = %08lx pc = %08lx\n", __func__,
>> +             ctrl->vrs[FP], ctrl->vrs[SP], ctrl->vrs[LR], ctrl->vrs[PC]);
>
> Minor-ish nit: you now duplicate this same pr_debug() in many places.
> Apologies, I didn't spot that in the previous review.
>
> What about something like this:
>
> static int unwind_exec_insn(...)
> {
>         int ret = URC_OK;
>
>         } else if (...)
>                 ret = unwind_exec_pop_subset_r4_to_r13(...);
>                 if (ret)
>                         goto error;
>         else ...
>
>         pr_debug(...);
>
> error:
>         return ret;
> }
>
> Then everything returns through the same pr_debug() after the insn has
> been executed.
>
> [...]
>
>> @@ -329,13 +382,13 @@ static int unwind_exec_insn(struct unwind_ctrl_block *ctrl)
>>   */
>>  int unwind_frame(struct stackframe *frame)
>>  {
>> -     unsigned long high, low;
>> +     unsigned long low;
>>       const struct unwind_idx *idx;
>>       struct unwind_ctrl_block ctrl;
>>
>> -     /* only go to a higher address on the stack */
>> +     /* store the highest address on the stack to avoid crossing it*/
>>       low = frame->sp;
>> -     high = ALIGN(low, THREAD_SIZE);
>> +     ctrl.sp_high = ALIGN(low, THREAD_SIZE);
>
> Does the code check anywhere that SP is word-aligned?
>
> That should probably be checked if it's not done already.
>
> I have some unrelated changes I want to make in this file (which is
> part of why I'm being pushy about getting things nice and clean) ... so
> I'm happy to follow up with that as a separate patch later.  It's a
> separate issue, really.  It doesn't necessarily belong in this patch.
>
> Cheers
> ---Dave



-- 
Anurag Aggarwal

Re: [PATCH V4] ARM : unwinder : Prevent data abort due to stack overflow

[Dave Martin]

On Thu, Dec 05, 2013 at 03:15:22PM +0000, Anurag Aggarwal wrote:
> >>if (unlikely(check) &&
> >>    *vsp >= (unsigned long *)ctrl->sp_high))
> 
> Good idea, It can help in optimizing the code and will leave code more readable
> and it will be easy to maintain also.

That was my goal -- it's not always easy to achieve both, but we should
try where possible, especially for non-performance-critical code.

> >>Does the code check anywhere that SP is word-aligned?
> >>
> >>That should probably be checked if it's not done already.
> 
> I think this should be handled in separate patch
> I would also like to hear more your ideas for the file

There are some limitations on how backtracing works with ARM_UNWIND.
The backtracer interface assumes that the compiler's register use with
ARM_UNWIND is "almost the same" as with !ARM_UNWIND.  But this is not
always true, and we've seen some problems.  

I think the best solution will involve some refactoring of the interface
between the backtracer and the unwinder backends, but I don't have it
all figured out yet...

Cheers
---Dave