Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Sat, Apr 20, 2019 at 12:15:26PM -0700, Cong Wang wrote: > Yes, one is V1 and the other is V2. Is it hard to understand V2 is to > replace V1? Well, looking at these two very different fixes, it made me think that you don't really know what you're doing. So I went and did the Knuth's version just so that I can analyze and understand the issue myself. The final result ended up needing *both* the index fix *and* removed the trailing noodling code after the loop which looked fishy at best and I wanted it gone anyway. So in the end: 1. your first fix was correct but incomplete 2. your second was replaced by a better version of the whole thing So the final result is a lot cleaner and straight-forward. And it is only 29 lines and I don't see a problem with it going to stable. And I as author and maintainer of this code have very much the prerogative to decide which way to go, TYVM. No matter how much you passive-aggressively bitch. Thanks to your last mail, I won't have to make this choice anymore. -- Regards/Gruss, Boris. Good mailing practices for 400: avoid top-posting and trim the reply.
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Sat, Apr 20, 2019 at 12:04 PM Borislav Petkov wrote: > > On Sat, Apr 20, 2019 at 11:25:43AM -0700, Cong Wang wrote: > > If you want to go that far, you can choose to use lib/bsearch.c too in > > case you want to reinvent the wheel. > > Well, that doesn't give me the @to functionality which points to the > slot where the new element should be inserted, when the search was > unsuccessful. No one stops you from adding it, as you are going far you can always go further. :) > > > What's your point here? > > My point is to fix it properly. Obviously. Of course, no one can stop you from rewriting the whole ras code by doing it properly. > > > You know my fix is targeted for -stable, > > Well, first you sent me this: > > https://lkml.kernel.org/r/20190416012001.5338-1-xiyou.wangc...@gmail.com > > then this: > > https://lkml.kernel.org/r/20190416213351.28999-1-xiyou.wangc...@gmail.com Yes, one is V1 and the other is V2. Is it hard to understand V2 is to replace V1? > > Tony liked this second version more and if you look at the final result of > mine: Sorry, I have no reason to look into a 83-line change. > it has basically *both*: the correct [min:max] range *and* the return of > ithe ndex when found. But the algorithm this time is the correct one. I don't review it, so I don't know. Feel free to believe you are correct here, until someone finds a bug later. > > > I doubt your 83-line change could fit for -stable. > > My 83-line change has debug output only for experimentation. It will, > *of* *course* be removed before committing it upstream. That's why I > called it "a conglomerate patch" and I said "It has some debug output > for easier debugging, that will be removed in the final version, of > course." I guess you didn't read that either. Why should I read a debugging patch? > > And the sanity_check() piece will be a separate patch, of course. > > In the end the diffstat will be 30-40 lines max. > > > Feel free to drop my patch to favor yours. I am really tired. > > Suit yourself. Thanks for the reporting. There is no bug here, your code is perfect. :) Sorry for wasting your time to believe this it is bug, it is not. :-) Thanks.
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Sat, Apr 20, 2019 at 11:25:43AM -0700, Cong Wang wrote:
> If you want to go that far, you can choose to use lib/bsearch.c too in
> case you want to reinvent the wheel.
Well, that doesn't give me the @to functionality which points to the
slot where the new element should be inserted, when the search was
unsuccessful.
> What's your point here?
My point is to fix it properly. Obviously.
> You know my fix is targeted for -stable,
Well, first you sent me this:
https://lkml.kernel.org/r/20190416012001.5338-1-xiyou.wangc...@gmail.com
then this:
https://lkml.kernel.org/r/20190416213351.28999-1-xiyou.wangc...@gmail.com
Tony liked this second version more and if you look at the final result of mine:
int min = 0, max = ca->n - 1;
...
if (this_pfn < pfn)
min = i + 1;
else if (this_pfn > pfn)
max = i - 1;
else if (this_pfn == pfn) {
if (to)
*to = i;
return i;
}
it has basically *both*: the correct [min:max] range *and* the return of
ithe ndex when found. But the algorithm this time is the correct one.
> I doubt your 83-line change could fit for -stable.
My 83-line change has debug output only for experimentation. It will,
*of* *course* be removed before committing it upstream. That's why I
called it "a conglomerate patch" and I said "It has some debug output
for easier debugging, that will be removed in the final version, of
course." I guess you didn't read that either.
And the sanity_check() piece will be a separate patch, of course.
In the end the diffstat will be 30-40 lines max.
> Feel free to drop my patch to favor yours. I am really tired.
Suit yourself. Thanks for the reporting.
> Good luck with that!
Ditto.
--
Regards/Gruss,
Boris.
Good mailing practices for 400: avoid top-posting and trim the reply.
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Sat, Apr 20, 2019 at 4:34 AM Borislav Petkov wrote: > > On Tue, Apr 16, 2019 at 04:16:08PM -0700, Cong Wang wrote: > > It is actually fairly easy: > > > > 1) Fill the whole page with PFN's: > > for i in `seq 0 511`; do echo $i >> /sys/kernel/debug/ras/cec/pfn; done > > > > 2) Set thresh to 1 in order to trigger the deletion: > > echo 1 > /sys/kernel/debug/ras/cec/count_threshold > > > > 3) Repeatedly add and remove the last element: > > echo 512 >> /sys/kernel/debug/ras/cec/pfn > > (until you get a crash.) > > Thanks, I was able to reproduce with that. Below is a conglomerate patch > which converts __find_elem() to using Donald Knuth's binary search > version. I don't know what I was thinking then and why I didn't use > it from the get-go. The textbook even says that one can easily get it > wrong... If you want to go that far, you can choose to use lib/bsearch.c too in case you want to reinvent the wheel. What's your point here? You know my fix is targeted for -stable, I doubt your 83-line change could fit for -stable. Feel free to drop my patch to favor yours. I am really tired. Good luck with that! Thanks.
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Tue, Apr 16, 2019 at 04:16:08PM -0700, Cong Wang wrote:
> It is actually fairly easy:
>
> 1) Fill the whole page with PFN's:
> for i in `seq 0 511`; do echo $i >> /sys/kernel/debug/ras/cec/pfn; done
>
> 2) Set thresh to 1 in order to trigger the deletion:
> echo 1 > /sys/kernel/debug/ras/cec/count_threshold
>
> 3) Repeatedly add and remove the last element:
> echo 512 >> /sys/kernel/debug/ras/cec/pfn
> (until you get a crash.)
Thanks, I was able to reproduce with that. Below is a conglomerate patch
which converts __find_elem() to using Donald Knuth's binary search
version. I don't know what I was thinking then and why I didn't use
it from the get-go. The textbook even says that one can easily get it
wrong...
Anyway, see below. It has some debug output for easier debugging, that
will be removed in the final version, of course. With it, the injection
pattern above works as expected and I'll continue hammering on it to see
if there are more funky issues.
For easier experimenting, the whole branch is also here:
https://git.kernel.org/pub/scm/linux/kernel/git/bp/bp.git/log/?h=tip-ras-core-cec
Thx.
---
From: Borislav Petkov
Date: Sat, 20 Apr 2019 13:27:51 +0200
Subject: [PATCH] WIP
Signed-off-by: Borislav Petkov
---
drivers/ras/cec.c | 83 +++
1 file changed, 62 insertions(+), 21 deletions(-)
diff --git a/drivers/ras/cec.c b/drivers/ras/cec.c
index 3e9f62b84378..946e52751ae2 100644
--- a/drivers/ras/cec.c
+++ b/drivers/ras/cec.c
@@ -185,31 +185,42 @@ static void cec_work_fn(struct work_struct *work)
*/
static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to)
{
+ int min = 0, max = ca->n - 1;
u64 this_pfn;
- int min = 0, max = ca->n;
- while (min < max) {
- int tmp = (max + min) >> 1;
+ pr_info("%s: entry %llu in [%d:%d]?\n", __func__, pfn, min, max);
- this_pfn = PFN(ca->array[tmp]);
+ while (min <= max) {
+ int i = (min + max) >> 1;
+
+ this_pfn = PFN(ca->array[i]);
+
+ pr_info("%s: ... this_pfn: %3llu, [%3d:%3d:%3d]\n",
+ __func__, this_pfn, min, i, max);
if (this_pfn < pfn)
- min = tmp + 1;
+ min = i + 1;
else if (this_pfn > pfn)
- max = tmp;
- else {
- min = tmp;
- break;
+ max = i - 1;
+ else if (this_pfn == pfn) {
+ pr_info("%s: .. FOUND at %d\n", __func__, i);
+
+ if (to)
+ *to = i;
+
+ return i;
}
}
- if (to)
- *to = min;
-
- this_pfn = PFN(ca->array[min]);
+ /*
+* When the loop terminates without finding @pfn, min has the index of
+* the element slot where the new @pfn should be inserted.
+*/
- if (this_pfn == pfn)
- return min;
+ if (to) {
+ *to = min;
+ pr_info("%s: [%d:%d]\n", __func__, min, max);
+ }
return -ENOKEY;
}
@@ -234,6 +245,8 @@ static void del_elem(struct ce_array *ca, int idx)
(ca->n - (idx + 1)) * sizeof(u64));
ca->n--;
+
+ pr_info("%s: idx: %d, ca->n: %d\n", __func__, idx, ca->n);
}
static u64 del_lru_elem_unlocked(struct ce_array *ca)
@@ -274,13 +287,43 @@ static u64 __maybe_unused del_lru_elem(void)
return pfn;
}
+static bool sanity_check(struct ce_array *ca)
+{
+ bool ret = false;
+ u64 prev = 0;
+ int i;
+
+ for (i = 0; i < ca->n; i++) {
+ u64 this = PFN(ca->array[i]);
+
+ if (WARN(prev > this, "prev: 0x%016llx <-> this: 0x%016llx\n",
prev, this))
+ ret = true;
+
+ prev = this;
+ }
+
+ if (!ret)
+ return ret;
+
+ pr_info("Sanity check:\n{ n: %d\n", ca->n);
+ for (i = 0; i < ca->n; i++) {
+ u64 this = PFN(ca->array[i]);
+ pr_info(" %03d: [%016llx|%03llx]\n", i, this,
FULL_COUNT(ca->array[i]));
+ }
+ pr_info("}\n");
+
+ return ret;
+}
int cec_add_elem(u64 pfn)
{
struct ce_array *ca = &ce_arr;
- unsigned int to;
+ unsigned int to = 0;
int count, ret = 0;
+ pr_info("===\n");
+ pr_info("%s: entry, pfn: %lld, ca->n: %d\n", __func__, pfn, ca->n);
+
/*
* We can be called very early on the identify_cpu() path where we are
* not initialized yet. We ignore the error for simplicity.
@@ -296,6 +339,7 @@ int cec_add_elem(u64 pfn)
WARN_ON(!del_lru_elem_unlocked(ca));
ret = find_elem(ca, pfn, &to);
+ pr_info("%s: find_elem: ret: %d: to: %d\n", __func__, ret, to);
if (ret < 0)
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Tue, Apr 16, 2019 at 2:46 PM Borislav Petkov wrote: > > On Tue, Apr 16, 2019 at 02:33:50PM -0700, Cong Wang wrote: > > ce_arr.array[] is always within the range [0, ce_arr.n-1]. > > However, the binary search code in __find_elem() uses ce_arr.n > > as the maximum index, which could lead to an off-by-one > > out-of-bound access right after the while loop. In this case, > > we should not even read it, just return -ENOKEY instead. > > > > Note, this could cause a kernel crash if ce_arr.n is exactly > > MAX_ELEMS. > > "Could cause"? > > I'm still waiting for a demonstration. You can build a case through > writing values in the debugfs nodes I pointed you at or even with a > patch ontop preparing the exact conditions for it to crash. And then > give me that "recipe" to trigger it here in a VM. It is actually fairly easy: 1) Fill the whole page with PFN's: for i in `seq 0 511`; do echo $i >> /sys/kernel/debug/ras/cec/pfn; done 2) Set thresh to 1 in order to trigger the deletion: echo 1 > /sys/kernel/debug/ras/cec/count_threshold 3) Repeatedly add and remove the last element: echo 512 >> /sys/kernel/debug/ras/cec/pfn (until you get a crash.) In case you still don't get it, here it is: [ 57.732593] BUG: unable to handle kernel paging request at 9c667bca [ 57.734994] #PF error: [PROT] [WRITE] [ 57.735891] PGD 75601067 P4D 75601067 PUD 75605067 PMD 7bca1063 PTE 80007bca0061 [ 57.737702] Oops: 0003 [#1] SMP PTI [ 57.738533] CPU: 0 PID: 649 Comm: bash Not tainted 5.1.0-rc5+ #561 [ 57.739965] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS ?-20180724_192412-buildhw-07.phx2.fedoraproject.org-1.fc29 04/01/2014 [ 57.742892] RIP: 0010:__memmove+0x57/0x1a0 [ 57.743853] Code: 00 72 05 40 38 fe 74 3b 48 83 ea 20 48 83 ea 20 4c 8b 1e 4c 8b 56 08 4c 8b 4e 10 4c 8b 46 18 48 8d 76 20 4c 89 1f 4c 89 57 08 <4c> 89 4f 10 4c 89 47 18 48 8d 7f 20 73 d4 48 83 c2 20 e9 a2 00 00 [ 57.748150] RSP: 0018:be2ec0c8bdf8 EFLAGS: 00010206 [ 57.749371] RAX: 9c667a5c1ff0 RBX: 0001 RCX: 0ff8 [ 57.751018] RDX: 0007fe921fb8 RSI: 9c667bca0018 RDI: 9c667bc9fff0 [ 57.752674] RBP: 0200 R08: R09: 015c [ 57.754325] R10: 00040001 R11: 5a5a5a5a5a5a5a5a R12: 0004 [ 57.755976] R13: 9c6671787778 R14: 9c6671787728 R15: 9c6671787750 [ 57.757631] FS: 7f33ca294740() GS:9c667d80() knlGS: [ 57.759689] CS: 0010 DS: ES: CR0: 80050033 [ 57.761023] CR2: 9c667bca CR3: 7061e000 CR4: 000406f0 [ 57.762681] Call Trace: [ 57.763275] del_elem.constprop.1+0x39/0x40 [ 57.764260] cec_add_elem+0x1e4/0x211 [ 57.765129] simple_attr_write+0xa2/0xc3 [ 57.766057] debugfs_attr_write+0x45/0x5c [ 57.767005] full_proxy_write+0x4b/0x65 [ 57.767911] ? full_proxy_poll+0x50/0x50 [ 57.768844] vfs_write+0xb8/0xf5 [ 57.769613] ksys_write+0x6b/0xb8 [ 57.770407] do_syscall_64+0x57/0x65 [ 57.771249] entry_SYSCALL_64_after_hwframe+0x49/0xbe I will leave it as a homework for explaining why the crash is inside memmove(). ;) Thanks.
Re: [PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
On Tue, Apr 16, 2019 at 02:33:50PM -0700, Cong Wang wrote: > ce_arr.array[] is always within the range [0, ce_arr.n-1]. > However, the binary search code in __find_elem() uses ce_arr.n > as the maximum index, which could lead to an off-by-one > out-of-bound access right after the while loop. In this case, > we should not even read it, just return -ENOKEY instead. > > Note, this could cause a kernel crash if ce_arr.n is exactly > MAX_ELEMS. "Could cause"? I'm still waiting for a demonstration. You can build a case through writing values in the debugfs nodes I pointed you at or even with a patch ontop preparing the exact conditions for it to crash. And then give me that "recipe" to trigger it here in a VM. Thx. -- Regards/Gruss, Boris. Good mailing practices for 400: avoid top-posting and trim the reply.
[PATCH v2 1/2] ras: fix an off-by-one error in __find_elem()
ce_arr.array[] is always within the range [0, ce_arr.n-1].
However, the binary search code in __find_elem() uses ce_arr.n
as the maximum index, which could lead to an off-by-one
out-of-bound access right after the while loop. In this case,
we should not even read it, just return -ENOKEY instead.
Note, this could cause a kernel crash if ce_arr.n is exactly
MAX_ELEMS.
Fixes: 011d82611172 ("RAS: Add a Corrected Errors Collector")
Cc: Tony Luck
Cc: Borislav Petkov
Cc: Thomas Gleixner
Signed-off-by: Cong Wang
---
drivers/ras/cec.c | 9 +
1 file changed, 5 insertions(+), 4 deletions(-)
diff --git a/drivers/ras/cec.c b/drivers/ras/cec.c
index 2d9ec378a8bc..a4ff54e50673 100644
--- a/drivers/ras/cec.c
+++ b/drivers/ras/cec.c
@@ -204,10 +204,11 @@ static int __find_elem(struct ce_array *ca, u64 pfn,
unsigned int *to)
if (to)
*to = min;
- this_pfn = PFN(ca->array[min]);
-
- if (this_pfn == pfn)
- return min;
+ if (min < ca->n) {
+ this_pfn = PFN(ca->array[min]);
+ if (this_pfn == pfn)
+ return min;
+ }
return -ENOKEY;
}
--
2.20.1
