From 70dbe86e544bdbcb43398a9782f94a4e0b2d311a Mon Sep 17 00:00:00 2001 From: Greg Kroah-Hartman Date: Mon, 17 Jun 2019 11:29:24 +0200 Subject: [PATCH] 4.14-stable patches added patches: ras-cec-fix-binary-search-function.patch --- .../ras-cec-fix-binary-search-function.patch | 91 +++++++++++++++++++ queue-4.14/series | 1 + 2 files changed, 92 insertions(+) create mode 100644 queue-4.14/ras-cec-fix-binary-search-function.patch diff --git a/queue-4.14/ras-cec-fix-binary-search-function.patch b/queue-4.14/ras-cec-fix-binary-search-function.patch new file mode 100644 index 00000000000..64b2321f187 --- /dev/null +++ b/queue-4.14/ras-cec-fix-binary-search-function.patch @@ -0,0 +1,91 @@ +From f3c74b38a55aefe1004200d15a83f109b510068c Mon Sep 17 00:00:00 2001 +From: Borislav Petkov +Date: Sat, 20 Apr 2019 13:27:51 +0200 +Subject: RAS/CEC: Fix binary search function + +From: Borislav Petkov + +commit f3c74b38a55aefe1004200d15a83f109b510068c upstream. + +Switch to using Donald Knuth's binary search algorithm (The Art of +Computer Programming, vol. 3, section 6.2.1). This should've been done +from the very beginning but the author must've been smoking something +very potent at the time. + +The problem with the current one was that it would return the wrong +element index in certain situations: + + https://lkml.kernel.org/r/CAM_iQpVd02zkVJ846cj-Fg1yUNuz6tY5q1Vpj4LrXmE06dPYYg@mail.gmail.com + +and the noodling code after the loop was fishy at best. + +So switch to using Knuth's binary search. The final result is much +cleaner and straightforward. + +Fixes: 011d82611172 ("RAS: Add a Corrected Errors Collector") +Reported-by: Cong Wang +Signed-off-by: Borislav Petkov +Cc: Tony Luck +Cc: linux-edac +Cc: +Signed-off-by: Greg Kroah-Hartman + +--- + drivers/ras/cec.c | 34 ++++++++++++++++++++-------------- + 1 file changed, 20 insertions(+), 14 deletions(-) + +--- a/drivers/ras/cec.c ++++ b/drivers/ras/cec.c +@@ -185,32 +185,38 @@ static void cec_timer_fn(unsigned long d + */ + 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; ++ while (min <= max) { ++ int i = (min + max) >> 1; + +- this_pfn = PFN(ca->array[tmp]); ++ this_pfn = PFN(ca->array[i]); + + 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) { ++ if (to) ++ *to = i; ++ ++ return i; + } + } + ++ /* ++ * When the loop terminates without finding @pfn, min has the index of ++ * the element slot where the new @pfn should be inserted. The loop ++ * terminates when min > max, which means the min index points to the ++ * bigger element while the max index to the smaller element, in-between ++ * which the new @pfn belongs to. ++ * ++ * For more details, see exercise 1, Section 6.2.1 in TAOCP, vol. 3. ++ */ + if (to) + *to = min; + +- this_pfn = PFN(ca->array[min]); +- +- if (this_pfn == pfn) +- return min; +- + return -ENOKEY; + } + diff --git a/queue-4.14/series b/queue-4.14/series index 8b2ad563705..48e626341f3 100644 --- a/queue-4.14/series +++ b/queue-4.14/series @@ -47,3 +47,4 @@ usb-usb-storage-add-new-id-to-ums-realtek.patch usb-serial-pl2303-add-allied-telesis-vt-kit3.patch usb-serial-option-add-support-for-simcom-sim7500-sim7600-rndis-mode.patch usb-serial-option-add-telit-0x1260-and-0x1261-compositions.patch +ras-cec-fix-binary-search-function.patch -- 2.47.3