All of lore.kernel.org
 help / color / mirror / Atom feed
From: James Hogan <james.hogan@imgtec.com>
To: Rabin Vincent <rabin.vincent@axis.com>
Cc: <ralf@linux-mips.org>, <linux-mips@linux-mips.org>,
	Rabin Vincent <rabinv@axis.com>
Subject: Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
Date: Tue, 4 Apr 2017 21:32:19 +0100	[thread overview]
Message-ID: <20170404203219.GK31606@jhogan-linux.le.imgtec.org> (raw)
In-Reply-To: <1491291731-5797-1-git-send-email-rabin.vincent@axis.com>

[-- 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 --]

WARNING: multiple messages have this Message-ID
From: James Hogan <james.hogan@imgtec.com>
To: Rabin Vincent <rabin.vincent@axis.com>
Cc: ralf@linux-mips.org, linux-mips@linux-mips.org,
	Rabin Vincent <rabinv@axis.com>
Subject: Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access
Date: Tue, 4 Apr 2017 21:32:19 +0100	[thread overview]
Message-ID: <20170404203219.GK31606@jhogan-linux.le.imgtec.org> (raw)
Message-ID: <20170404203219.bYTk22vPquoTIF2KNQqFXT1pFze7hzKN4TwBL5qGUnQ@z> (raw)
In-Reply-To: <1491291731-5797-1-git-send-email-rabin.vincent@axis.com>

[-- 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 --]

  reply	other threads:[~2017-04-04 20:32 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-04-04  7:42 Rabin Vincent
2017-04-04 20:32 ` James Hogan [this message]
2017-04-04 20:32   ` James Hogan
2017-04-05 13:08   ` Rabin Vincent

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20170404203219.GK31606@jhogan-linux.le.imgtec.org \
    --to=james.hogan@imgtec.com \
    --cc=linux-mips@linux-mips.org \
    --cc=rabin.vincent@axis.com \
    --cc=rabinv@axis.com \
    --cc=ralf@linux-mips.org \
    --subject='Re: [PATCH] MIPS: cevt-r4k: fix array out-of-bounds access' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

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.