* [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 related [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 related [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 related [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.