lib/extable.c: use bsearch() library function in search_extable()
Subsystems (4)
PATCH v3 1/1 lib/extable.c: use bsearch() library function in search_extable()
v3: Fix arch specific implementations
Signed-off-by Thomas Meyer <[email protected]>
--- arch/mips/kernel/module.c | 3 ++- arch/mips/kernel/traps.c | 3 ++- arch/sh/mm/extable_64.c | 34 ++++++++++++++++++---------------- arch/sparc/mm/extable.c | 28 ++++++++++++++-------------- include/linux/extable.h | 5 +++-- kernel/extable.c | 3 ++- kernel/module.c | 2 +- lib/extable.c | 41 +++++++++++++++++++++-------------------- 8 files changed, 63 insertions(+), 56 deletions(-)
arch/mips/kernel/module.c +2 -1
@@ -317,7 +317,8 @@ const struct exception_table_entry *search_module_dbetables(unsigned long addr)spin_lock_irqsave (&dbe_lock, flags);list_for_each_entry (dbe, &dbe_list, dbe_list) { - e =search_extable (dbe->dbe_start, dbe->dbe_end -1 , addr); + e =search_extable (dbe->dbe_start, + dbe->dbe_end - dbe->dbe_start, addr);if (e)break ; }
arch/mips/kernel/traps.c +2 -1
@@ -427,7 +427,8 @@ static const struct exception_table_entry *search_dbe_tables(unsigned long addr) {const struct exception_table_entry *e; - e =search_extable (__start___dbe_table, __stop___dbe_table -1 , addr); + e =search_extable (__start___dbe_table, + __stop___dbe_table - __start___dbe_table, addr);if (!e) e =search_module_dbetables (addr);return e;
arch/sh/mm/extable_64.c +18 -16
@@ -10,6 +10,7 @@* License. See the file "COPYING" in the main directory of this archive * for more details. */ +#include <linux/bsearch.h> #include <linux/rwsem.h> #include <linux/extable.h> #include <linux/uaccess.h>
@@ -40,10 +41,23 @@ static const struct exception_table_entry *check_exception_ranges(unsigned longreturn NULL ; } +static int cmp_ex_search (const void *key,const void *elt) +{ +const struct exception_table_entry *_elt = elt; +unsigned long _key = *(unsigned long *)key; + +/* avoid overflow */ +if (_key > _elt->insn) +return 1 ; +if (_key < _elt->insn) +return -1 ; +return 0 ; +} +/* Simple binary search */ const struct exception_table_entry * -search_extable (const struct exception_table_entry *first, -const struct exception_table_entry *last, +search_extable (const struct exception_table_entry *base, +const size_t num,unsigned long value) {const struct exception_table_entry *mid;
@@ -52,20 +66,8 @@ search_extable(const struct exception_table_entry *first,if (mid)return mid; -while (first <= last) { -long diff; - - mid = (last - first) /2 + first; - diff = mid->insn - value; -if (diff ==0 ) -return mid; -else if (diff <0 ) - first = mid+1 ; -else - last = mid-1 ; - } - -return NULL ; +return bsearch (&value, base, num, +sizeof (struct exception_table_entry ), cmp_ex_search); }int fixup_exception (struct pt_regs *regs)
arch/sparc/mm/extable.c +14 -14
@@ -13,11 +13,11 @@ void sort_extable(struct exception_table_entry *start,/* Caller knows they are in a range if ret->fixup == 0 */ const struct exception_table_entry * -search_extable (const struct exception_table_entry *start, -const struct exception_table_entry *last, +search_extable (const struct exception_table_entry *base, +const size_t num,unsigned long value) { -const struct exception_table_entry *walk; +int i;/* Single insn entries are encoded as: * word 1: insn address
@@ -37,30 +37,30 @@ search_extable(const struct exception_table_entry *start,*/ /* 1. Try to find an exact match. */ -for (walk = start; walk <= last; walk++) { -if (walk->fixup ==0 ) { +for (i =0 ; i < num; i++) { +if (base[i].fixup ==0 ) {/* A range entry, skip both parts. */ - walk++; + i++;continue ; }/* A deleted entry; see trim_init_extable */ -if (walk->fixup ==-1 ) +if (base[i].fixup ==-1 )continue ; -if (walk->insn == value) -return walk; +if (base[i].insn == value) +return &base[i]; }/* 2. Try to find a range match. */ -for (walk = start; walk <= (last -1 ); walk++) { -if (walk->fixup) +for (i =0 ; i < (num -1 ); i++) { +if (base[i].fixup)continue ; -if (walk[0 ].insn <= value && walk[1 ].insn > value) -return walk; +if (base[i].insn <= value && base[i +1 ].insn > value) +return &base[i]; - walk++; + i++; }return NULL ;
include/linux/extable.h +3 -2
@@ -2,13 +2,14 @@#define _LINUX_EXTABLE_H#include <linux/stddef.h> /* for NULL */ +#include <linux/types.h> struct module ;struct exception_table_entry ;const struct exception_table_entry * -search_extable (const struct exception_table_entry *first, -const struct exception_table_entry *last, +search_extable (const struct exception_table_entry *base, +const size_t num,unsigned long value);void sort_extable (struct exception_table_entry *start,struct exception_table_entry *finish);
kernel/extable.c +2 -1
@@ -55,7 +55,8 @@ const struct exception_table_entry *search_exception_tables(unsigned long addr) {const struct exception_table_entry *e; - e =search_extable (__start___ex_table, __stop___ex_table-1 , addr); + e =search_extable (__start___ex_table, + __stop___ex_table - __start___ex_table, addr);if (!e) e =search_module_extables (addr);return e;
kernel/module.c +1 -1
@@ -4201,7 +4201,7 @@ const struct exception_table_entry *search_module_extables(unsigned long addr) goto out; e =search_extable (mod->extable, - mod->extable + mod->num_exentries -1 , + mod->num_exentries, addr); out:preempt_enable ();
lib/extable.c +21 -20
72 lines not on this page · raw message