All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
@ 2017-04-04  7:42 Rabin Vincent
  2017-04-04 20:32   ` James Hogan
  0 siblings, 1 reply; 4+ messages in thread
From: Rabin Vincent @ 2017-04-04  7:42 UTC (permalink / raw)
  To: ralf; +Cc: james.hogan, linux-mips, Rabin Vincent

From: Rabin Vincent <rabinv@axis.com>

calculate_min_delta() tries to access a fourth element of buf2 but the
array has only three elements.  This triggers undefined behaviour and
causes strange crashes in start_kernel() sometime after timer
initialization, when built with GCC 5.3, probably due to register/stack
corruption:

 sched_clock: 32 bits at 200MHz, resolution 5ns, wraps every 10737418237ns
 CPU 0 Unable to handle kernel paging request at virtual address ffffb0aa,
       epc == 8067daa8, ra == 8067da84
 Oops[#1]:
 CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #51
 task: 8065e3e0 task.stack: 80644000
 $ 0   : 00000000 00000001 00000000 00000000
 $ 4   : 8065b4d0 00000000 805d0000 00000010
 $ 8   : 00000010 80321400 fffff000 812de408
 $12   : 00000000 00000000 00000000 ffffffff
 $16   : 00000002 ffffffff 80660000 806a666c
 $20   : 806c0000 00000000 00000000 00000000
 $24   : 00000000 00000010
 $28   : 80644000 80645ed0 00000000 8067da84
 Hi    : 00000000
 Lo    : 00000000
 epc   : 8067daa8 start_kernel+0x33c/0x500
 ra    : 8067da84 start_kernel+0x318/0x500
 Status: 11000402 KERNEL EXL
 Cause : 4080040c (ExcCode 03)
 BadVA : ffffb0aa
 PrId  : 0501992c (MIPS 1004Kc)
 Modules linked in:
 Process swapper/0 (pid: 0, threadinfo=80644000, task=8065e3e0, tls=00000000)
 Call Trace:
 [<8067daa8>] start_kernel+0x33c/0x500
 Code: 24050240  0c0131f9  24849c64 <a200b0a8> 41606020  000000c0  0c1a45e6
       00000000  0c1a5f44

UBSAN also detects it:

 ================================================================
 UBSAN: Undefined behaviour in arch/mips/kernel/cevt-r4k.c:85:41
 load of address 80647e4c with insufficient space
 for an object of type 'unsigned int'
 CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #47
 Call Trace:
 [<80028f70>] show_stack+0x88/0xa4
 [<80312654>] dump_stack+0x84/0xc0
 [<8034163c>] ubsan_epilogue+0x14/0x50
 [<803417d8>] __ubsan_handle_type_mismatch+0x160/0x168
 [<8002dab0>] r4k_clockevent_init+0x544/0x764
 [<80684d34>] time_init+0x18/0x90
 [<8067fa5c>] start_kernel+0x2f0/0x500
 =================================================================

Fixes: 1fa405552e33f2 ("MIPS: cevt-r4k: Dynamically calculate min_delta_ns")
Signed-off-by: Rabin Vincent <rabinv@axis.com>
---
 arch/mips/kernel/cevt-r4k.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/mips/kernel/cevt-r4k.c b/arch/mips/kernel/cevt-r4k.c
index 804d2a2..723a1f1 100644
--- a/arch/mips/kernel/cevt-r4k.c
+++ b/arch/mips/kernel/cevt-r4k.c
@@ -48,7 +48,7 @@ static int mips_next_event(unsigned long delta,
 static unsigned int calculate_min_delta(void)
 {
 	unsigned int cnt, i, j, k, l;
-	unsigned int buf1[4], buf2[3];
+	unsigned int buf1[4], buf2[4];
 	unsigned int min_delta;
 
 	/*
-- 
2.7.0

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
@ 2017-04-04 20:32   ` James Hogan
  0 siblings, 0 replies; 4+ messages in thread
From: James Hogan @ 2017-04-04 20:32 UTC (permalink / raw)
  To: Rabin Vincent; +Cc: ralf, linux-mips, Rabin Vincent

[-- Attachment #1: Type: text/plain, Size: 4506 bytes --]

Hi Rabin,

On Tue, Apr 04, 2017 at 09:42:11AM +0200, Rabin Vincent wrote:
> From: Rabin Vincent <rabinv@axis.com>
> 
> calculate_min_delta() tries to access a fourth element of buf2 but the
> array has only three elements.  This triggers undefined behaviour and
> causes strange crashes in start_kernel() sometime after timer
> initialization, when built with GCC 5.3, probably due to register/stack
> corruption:
> 
>  sched_clock: 32 bits at 200MHz, resolution 5ns, wraps every 10737418237ns
>  CPU 0 Unable to handle kernel paging request at virtual address ffffb0aa,
>        epc == 8067daa8, ra == 8067da84
>  Oops[#1]:
>  CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #51
>  task: 8065e3e0 task.stack: 80644000
>  $ 0   : 00000000 00000001 00000000 00000000
>  $ 4   : 8065b4d0 00000000 805d0000 00000010
>  $ 8   : 00000010 80321400 fffff000 812de408
>  $12   : 00000000 00000000 00000000 ffffffff
>  $16   : 00000002 ffffffff 80660000 806a666c
>  $20   : 806c0000 00000000 00000000 00000000
>  $24   : 00000000 00000010
>  $28   : 80644000 80645ed0 00000000 8067da84
>  Hi    : 00000000
>  Lo    : 00000000
>  epc   : 8067daa8 start_kernel+0x33c/0x500
>  ra    : 8067da84 start_kernel+0x318/0x500
>  Status: 11000402 KERNEL EXL
>  Cause : 4080040c (ExcCode 03)
>  BadVA : ffffb0aa
>  PrId  : 0501992c (MIPS 1004Kc)
>  Modules linked in:
>  Process swapper/0 (pid: 0, threadinfo=80644000, task=8065e3e0, tls=00000000)
>  Call Trace:
>  [<8067daa8>] start_kernel+0x33c/0x500
>  Code: 24050240  0c0131f9  24849c64 <a200b0a8> 41606020  000000c0  0c1a45e6
>        00000000  0c1a5f44
> 
> UBSAN also detects it:
> 
>  ================================================================
>  UBSAN: Undefined behaviour in arch/mips/kernel/cevt-r4k.c:85:41
>  load of address 80647e4c with insufficient space
>  for an object of type 'unsigned int'
>  CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #47
>  Call Trace:
>  [<80028f70>] show_stack+0x88/0xa4
>  [<80312654>] dump_stack+0x84/0xc0
>  [<8034163c>] ubsan_epilogue+0x14/0x50
>  [<803417d8>] __ubsan_handle_type_mismatch+0x160/0x168
>  [<8002dab0>] r4k_clockevent_init+0x544/0x764
>  [<80684d34>] time_init+0x18/0x90
>  [<8067fa5c>] start_kernel+0x2f0/0x500
>  =================================================================

Hmm, good catch, thanks! Curious that a stray read would wreck such
havoc, but I suppose the compiler can do whatever weirdness it likes
after that. Clearly it shouldn't be doing that read in the first place. 

> 
> Fixes: 1fa405552e33f2 ("MIPS: cevt-r4k: Dynamically calculate min_delta_ns")
> Signed-off-by: Rabin Vincent <rabinv@axis.com>
> ---
>  arch/mips/kernel/cevt-r4k.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/arch/mips/kernel/cevt-r4k.c b/arch/mips/kernel/cevt-r4k.c
> index 804d2a2..723a1f1 100644
> --- a/arch/mips/kernel/cevt-r4k.c
> +++ b/arch/mips/kernel/cevt-r4k.c
> @@ -48,7 +48,7 @@ static int mips_next_event(unsigned long delta,
>  static unsigned int calculate_min_delta(void)
>  {
>  	unsigned int cnt, i, j, k, l;
> -	unsigned int buf1[4], buf2[3];
> +	unsigned int buf1[4], buf2[4];

I think the correct fix is to prevent the read rather than change the
size of the array. buf2[] is intentionally 3 so that out of 5 sorted
samples the last element is the median, whereas buf1 is 4 elements so as
to work out the 75th percentile.

When inserting the 5th sample into buf1 (i.e. j = 4), there are already
4 entries, so the highest element it needs to compare against is the 4th
one (buf1[k=3]), so thats fine.

For buf2 however its still trying to insert 5 elements, so by the 5th
one (i.e. i = 4) it may try to compare against the 4th element to know
whether to insert before it, at which point we simply don't care about
the ordering as its past the median.

So I think something like this would be more correct. Does that fix your
problem?

diff --git a/arch/mips/kernel/cevt-r4k.c b/arch/mips/kernel/cevt-r4k.c
index 804d2a2a19fe..dd6a18bc10ab 100644
--- a/arch/mips/kernel/cevt-r4k.c
+++ b/arch/mips/kernel/cevt-r4k.c
@@ -80,7 +80,7 @@ static unsigned int calculate_min_delta(void)
 		}
 
 		/* Sorted insert of 75th percentile into buf2 */
-		for (k = 0; k < i; ++k) {
+		for (k = 0; k < i && k < ARRAY_SIZE(buf2); ++k) {
 			if (buf1[ARRAY_SIZE(buf1) - 1] < buf2[k]) {
 				l = min_t(unsigned int,
 					  i, ARRAY_SIZE(buf2) - 1);

Thanks
James

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
@ 2017-04-04 20:32   ` James Hogan
  0 siblings, 0 replies; 4+ messages in thread
From: James Hogan @ 2017-04-04 20:32 UTC (permalink / raw)
  To: Rabin Vincent; +Cc: ralf, linux-mips, Rabin Vincent

[-- Attachment #1: Type: text/plain, Size: 4506 bytes --]

Hi Rabin,

On Tue, Apr 04, 2017 at 09:42:11AM +0200, Rabin Vincent wrote:
> From: Rabin Vincent <rabinv@axis.com>
> 
> calculate_min_delta() tries to access a fourth element of buf2 but the
> array has only three elements.  This triggers undefined behaviour and
> causes strange crashes in start_kernel() sometime after timer
> initialization, when built with GCC 5.3, probably due to register/stack
> corruption:
> 
>  sched_clock: 32 bits at 200MHz, resolution 5ns, wraps every 10737418237ns
>  CPU 0 Unable to handle kernel paging request at virtual address ffffb0aa,
>        epc == 8067daa8, ra == 8067da84
>  Oops[#1]:
>  CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #51
>  task: 8065e3e0 task.stack: 80644000
>  $ 0   : 00000000 00000001 00000000 00000000
>  $ 4   : 8065b4d0 00000000 805d0000 00000010
>  $ 8   : 00000010 80321400 fffff000 812de408
>  $12   : 00000000 00000000 00000000 ffffffff
>  $16   : 00000002 ffffffff 80660000 806a666c
>  $20   : 806c0000 00000000 00000000 00000000
>  $24   : 00000000 00000010
>  $28   : 80644000 80645ed0 00000000 8067da84
>  Hi    : 00000000
>  Lo    : 00000000
>  epc   : 8067daa8 start_kernel+0x33c/0x500
>  ra    : 8067da84 start_kernel+0x318/0x500
>  Status: 11000402 KERNEL EXL
>  Cause : 4080040c (ExcCode 03)
>  BadVA : ffffb0aa
>  PrId  : 0501992c (MIPS 1004Kc)
>  Modules linked in:
>  Process swapper/0 (pid: 0, threadinfo=80644000, task=8065e3e0, tls=00000000)
>  Call Trace:
>  [<8067daa8>] start_kernel+0x33c/0x500
>  Code: 24050240  0c0131f9  24849c64 <a200b0a8> 41606020  000000c0  0c1a45e6
>        00000000  0c1a5f44
> 
> UBSAN also detects it:
> 
>  ================================================================
>  UBSAN: Undefined behaviour in arch/mips/kernel/cevt-r4k.c:85:41
>  load of address 80647e4c with insufficient space
>  for an object of type 'unsigned int'
>  CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.9.18 #47
>  Call Trace:
>  [<80028f70>] show_stack+0x88/0xa4
>  [<80312654>] dump_stack+0x84/0xc0
>  [<8034163c>] ubsan_epilogue+0x14/0x50
>  [<803417d8>] __ubsan_handle_type_mismatch+0x160/0x168
>  [<8002dab0>] r4k_clockevent_init+0x544/0x764
>  [<80684d34>] time_init+0x18/0x90
>  [<8067fa5c>] start_kernel+0x2f0/0x500
>  =================================================================

Hmm, good catch, thanks! Curious that a stray read would wreck such
havoc, but I suppose the compiler can do whatever weirdness it likes
after that. Clearly it shouldn't be doing that read in the first place. 

> 
> Fixes: 1fa405552e33f2 ("MIPS: cevt-r4k: Dynamically calculate min_delta_ns")
> Signed-off-by: Rabin Vincent <rabinv@axis.com>
> ---
>  arch/mips/kernel/cevt-r4k.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/arch/mips/kernel/cevt-r4k.c b/arch/mips/kernel/cevt-r4k.c
> index 804d2a2..723a1f1 100644
> --- a/arch/mips/kernel/cevt-r4k.c
> +++ b/arch/mips/kernel/cevt-r4k.c
> @@ -48,7 +48,7 @@ static int mips_next_event(unsigned long delta,
>  static unsigned int calculate_min_delta(void)
>  {
>  	unsigned int cnt, i, j, k, l;
> -	unsigned int buf1[4], buf2[3];
> +	unsigned int buf1[4], buf2[4];

I think the correct fix is to prevent the read rather than change the
size of the array. buf2[] is intentionally 3 so that out of 5 sorted
samples the last element is the median, whereas buf1 is 4 elements so as
to work out the 75th percentile.

When inserting the 5th sample into buf1 (i.e. j = 4), there are already
4 entries, so the highest element it needs to compare against is the 4th
one (buf1[k=3]), so thats fine.

For buf2 however its still trying to insert 5 elements, so by the 5th
one (i.e. i = 4) it may try to compare against the 4th element to know
whether to insert before it, at which point we simply don't care about
the ordering as its past the median.

So I think something like this would be more correct. Does that fix your
problem?

diff --git a/arch/mips/kernel/cevt-r4k.c b/arch/mips/kernel/cevt-r4k.c
index 804d2a2a19fe..dd6a18bc10ab 100644
--- a/arch/mips/kernel/cevt-r4k.c
+++ b/arch/mips/kernel/cevt-r4k.c
@@ -80,7 +80,7 @@ static unsigned int calculate_min_delta(void)
 		}
 
 		/* Sorted insert of 75th percentile into buf2 */
-		for (k = 0; k < i; ++k) {
+		for (k = 0; k < i && k < ARRAY_SIZE(buf2); ++k) {
 			if (buf1[ARRAY_SIZE(buf1) - 1] < buf2[k]) {
 				l = min_t(unsigned int,
 					  i, ARRAY_SIZE(buf2) - 1);

Thanks
James

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
  2017-04-04 20:32   ` James Hogan
  (?)
@ 2017-04-05 13:08   ` Rabin Vincent
  -1 siblings, 0 replies; 4+ messages in thread
From: Rabin Vincent @ 2017-04-05 13:08 UTC (permalink / raw)
  To: James Hogan; +Cc: ralf, linux-mips

On Tue, Apr 04, 2017 at 09:32:19PM +0100, James Hogan wrote:
> I think the correct fix is to prevent the read rather than change the
> size of the array. buf2[] is intentionally 3 so that out of 5 sorted
> samples the last element is the median, whereas buf1 is 4 elements so as
> to work out the 75th percentile.
> 
> When inserting the 5th sample into buf1 (i.e. j = 4), there are already
> 4 entries, so the highest element it needs to compare against is the 4th
> one (buf1[k=3]), so thats fine.
> 
> For buf2 however its still trying to insert 5 elements, so by the 5th
> one (i.e. i = 4) it may try to compare against the 4th element to know
> whether to insert before it, at which point we simply don't care about
> the ordering as its past the median.
> 
> So I think something like this would be more correct. Does that fix your
> problem?

Yes, this fixes it too.  Please feel free to submit it yourself with
your explanation.  You can add my Tested-by if you like.

Thanks.

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2017-04-05 13:08 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-04-04  7:42 [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access Rabin Vincent
2017-04-04 20:32 ` James Hogan
2017-04-04 20:32   ` James Hogan
2017-04-05 13:08   ` Rabin Vincent

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.