Skip to contentSkip to conversation

parisc: unwind: Replace open-coded binary search with bsearch()

PATCH Applied Sean Young 2 participants 2 messages Sep 13 – Sep 15 PA-RISC architecture

lore
Share & tools
lore

Sean Young

author
#0 lore raw

PATCH 1/1 parisc: unwind: Replace open-coded binary search with bsearch()

There is a bug in the binary search where hi can underflow. If addr is less than the first entry, then "hi = mid - 1" will underflow to ULONG_MAX. Then we have an out-of-bounds read.

Replace the open-coded binary search with bsearch().

Issue found by an LLM.

---
 arch/parisc/kernel/unwind.c | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)
arch/parisc/kernel/unwind.c +15 -18
index 32103a270a8e..fab9ae22191a 100644
@@ -14,6 +14,7 @@
 #include <linux/sched.h>
 #include <linux/slab.h>
 #include <linux/sort.h>
+#include <linux/bsearch.h>
 #include <linux/sched/task_stack.h>
 
 #include <linux/uaccess.h>
@@ -49,27 +50,23 @@ static DEFINE_SPINLOCK(unwind_lock);
 static struct unwind_table kernel_unwind_table __ro_after_init;
 static LIST_HEAD(unwind_tables);
 
-static inline const struct unwind_table_entry *
-find_unwind_entry_in_table(const struct unwind_table *table, unsigned long addr)
+static int cmp_unwind_entry(const void *key, const void *elt)
 {
-	const struct unwind_table_entry *e = NULL;
-	unsigned long lo, hi, mid;
+	unsigned long addr = (unsigned long)key;
+	const struct unwind_table_entry *e = elt;
 
-	lo = 0; 
-	hi = table->length - 1; 
-	
-	while (lo <= hi) {
-		mid = (hi - lo) / 2 + lo;
-		e = &table->table[mid];
-		if (addr < e->region_start)
-			hi = mid - 1;
-		else if (addr > e->region_end)
-			lo = mid + 1;
-		else
-			return e;
-	}
+	if (addr < e->region_start)
+		return -1;
+	if (addr > e->region_end)
+		return 1;
+	return 0;
+}
 
-	return NULL;
+static inline const struct unwind_table_entry *
+find_unwind_entry_in_table(const struct unwind_table *table, unsigned long addr)
+{
+	return bsearch((void *)addr, table->table, table->length,
+		       sizeof(*table->table), cmp_unwind_entry);
 }
 
 static const struct unwind_table_entry *
Signature · 1 line
2.55.0
maintainer Applied
#1 lore raw
Quoted 4 lines · Sean Young

There is a bug in the binary search where hi can underflow. If addr is less than the first entry, then "hi = mid - 1" will underflow to ULONG_MAX. Then we have an out-of-bounds read.

Quoted 8 lines

Replace the open-coded binary search with bsearch().

Issue found by an LLM.

---
  arch/parisc/kernel/unwind.c | 33 +++++++++++++++------------------
  1 file changed, 15 insertions(+), 18 deletions(-)

Applied.

Thanks!
Helge