]>
Commit | Line | Data |
---|---|---|
4edac94b GKH |
1 | From f3c74b38a55aefe1004200d15a83f109b510068c Mon Sep 17 00:00:00 2001 |
2 | From: Borislav Petkov <bp@suse.de> | |
3 | Date: Sat, 20 Apr 2019 13:27:51 +0200 | |
4 | Subject: RAS/CEC: Fix binary search function | |
5 | ||
6 | From: Borislav Petkov <bp@suse.de> | |
7 | ||
8 | commit f3c74b38a55aefe1004200d15a83f109b510068c upstream. | |
9 | ||
10 | Switch to using Donald Knuth's binary search algorithm (The Art of | |
11 | Computer Programming, vol. 3, section 6.2.1). This should've been done | |
12 | from the very beginning but the author must've been smoking something | |
13 | very potent at the time. | |
14 | ||
15 | The problem with the current one was that it would return the wrong | |
16 | element index in certain situations: | |
17 | ||
18 | https://lkml.kernel.org/r/CAM_iQpVd02zkVJ846cj-Fg1yUNuz6tY5q1Vpj4LrXmE06dPYYg@mail.gmail.com | |
19 | ||
20 | and the noodling code after the loop was fishy at best. | |
21 | ||
22 | So switch to using Knuth's binary search. The final result is much | |
23 | cleaner and straightforward. | |
24 | ||
25 | Fixes: 011d82611172 ("RAS: Add a Corrected Errors Collector") | |
26 | Reported-by: Cong Wang <xiyou.wangcong@gmail.com> | |
27 | Signed-off-by: Borislav Petkov <bp@suse.de> | |
28 | Cc: Tony Luck <tony.luck@intel.com> | |
29 | Cc: linux-edac <linux-edac@vger.kernel.org> | |
30 | Cc: <stable@vger.kernel.org> | |
31 | Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> | |
32 | ||
33 | --- | |
34 | drivers/ras/cec.c | 34 ++++++++++++++++++++-------------- | |
35 | 1 file changed, 20 insertions(+), 14 deletions(-) | |
36 | ||
37 | --- a/drivers/ras/cec.c | |
38 | +++ b/drivers/ras/cec.c | |
39 | @@ -181,32 +181,38 @@ static void cec_work_fn(struct work_stru | |
40 | */ | |
41 | static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to) | |
42 | { | |
43 | + int min = 0, max = ca->n - 1; | |
44 | u64 this_pfn; | |
45 | - int min = 0, max = ca->n; | |
46 | ||
47 | - while (min < max) { | |
48 | - int tmp = (max + min) >> 1; | |
49 | + while (min <= max) { | |
50 | + int i = (min + max) >> 1; | |
51 | ||
52 | - this_pfn = PFN(ca->array[tmp]); | |
53 | + this_pfn = PFN(ca->array[i]); | |
54 | ||
55 | if (this_pfn < pfn) | |
56 | - min = tmp + 1; | |
57 | + min = i + 1; | |
58 | else if (this_pfn > pfn) | |
59 | - max = tmp; | |
60 | - else { | |
61 | - min = tmp; | |
62 | - break; | |
63 | + max = i - 1; | |
64 | + else if (this_pfn == pfn) { | |
65 | + if (to) | |
66 | + *to = i; | |
67 | + | |
68 | + return i; | |
69 | } | |
70 | } | |
71 | ||
72 | + /* | |
73 | + * When the loop terminates without finding @pfn, min has the index of | |
74 | + * the element slot where the new @pfn should be inserted. The loop | |
75 | + * terminates when min > max, which means the min index points to the | |
76 | + * bigger element while the max index to the smaller element, in-between | |
77 | + * which the new @pfn belongs to. | |
78 | + * | |
79 | + * For more details, see exercise 1, Section 6.2.1 in TAOCP, vol. 3. | |
80 | + */ | |
81 | if (to) | |
82 | *to = min; | |
83 | ||
84 | - this_pfn = PFN(ca->array[min]); | |
85 | - | |
86 | - if (this_pfn == pfn) | |
87 | - return min; | |
88 | - | |
89 | return -ENOKEY; | |
90 | } | |
91 |