linux-kernel - Re: [PATCH v2] lib/extable.c: use bsearch() library function in search

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-Id: <0DC18257-2DD4-4FF8-AE32-17A7B6A0DF0B@m3y3r.de>
Date:   Mon, 12 Jun 2017 00:18:17 +0200
From:   LKML <lkml@...3r.de>
To:     Thomas Meyer <thomas@...3r.de>
Cc:     Rasmus Villemoes <linux@...musvillemoes.dk>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] lib/extable.c: use bsearch() library function in search_extable()



With kind regards
Thomas

> Am 04.06.2017 um 00:38 schrieb Thomas Meyer <thomas@...3r.de>:
> 
> Signed-off-by: Thomas Meyer <thomas@...3r.de>
> ---
>  include/linux/extable.h |  3 ++-
>  kernel/extable.c        |  2 +-
>  kernel/module.c         |  2 +-
>  lib/extable.c           | 38 +++++++++++++++++++-------------------
>  4 files changed, 23 insertions(+), 22 deletions(-)
> 
> diff --git a/include/linux/extable.h b/include/linux/extable.h
> index 7effea4..b575bb9 100644
> --- a/include/linux/extable.h
> +++ b/include/linux/extable.h
> @@ -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,
> +           const size_t num,
>             unsigned long value);
>  void sort_extable(struct exception_table_entry *start,
>            struct exception_table_entry *finish);
> diff --git a/kernel/extable.c b/kernel/extable.c
> index 2676d7f..0c25b75 100644
> --- a/kernel/extable.c
> +++ b/kernel/extable.c
> @@ -55,7 +55,7 @@ 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;
> diff --git a/kernel/module.c b/kernel/module.c
> index 4a3665f..22faf11 100644
> --- a/kernel/module.c
> +++ b/kernel/module.c
> @@ -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();
> diff --git a/lib/extable.c b/lib/extable.c
> index 62968da..d4d3929 100644
> --- a/lib/extable.c
> +++ b/lib/extable.c
> @@ -9,6 +9,7 @@
>   * 2 of the License, or (at your option) any later version.
>   */
>  
> +#include <linux/bsearch.h>
>  #include <linux/module.h>
>  #include <linux/init.h>
>  #include <linux/sort.h>
> @@ -51,7 +52,7 @@ static void swap_ex(void *a, void *b, int size)
>   * This is used both for the kernel exception table and for
>   * the exception tables of modules that get loaded.
>   */
> -static int cmp_ex(const void *a, const void *b)
> +static int cmp_ex_sort(const void *a, const void *b)
>  {
>      const struct exception_table_entry *x = a, *y = b;
>  
> @@ -67,7 +68,7 @@ void sort_extable(struct exception_table_entry *start,
>            struct exception_table_entry *finish)
>  {
>      sort(start, finish - start, sizeof(struct exception_table_entry),
> -         cmp_ex, swap_ex);
> +         cmp_ex_sort, swap_ex);
>  }
>  
>  #ifdef CONFIG_MODULES
> @@ -93,6 +94,20 @@ void trim_init_extable(struct module *m)
>  #endif /* !ARCH_HAS_SORT_EXTABLE */
>  
>  #ifndef ARCH_HAS_SEARCH_EXTABLE
> +
> +static int cmp_ex_search(const void *key, const void *elt)
> +{
> +    const struct exception_table_entry * _elt = elt;
> +    unsigned long k = *(unsigned long*) key;
> +
> +    /* avoid overflow */
> +    if (k > ex_to_insn(_elt))
> +        return 1;
> +    if (k < ex_to_insn(_elt))
> +        return -1;
> +    return 0;
> +}
> +
>  /*
>   * Search one exception table for an entry corresponding to the
>   * given instruction address, and return the address of the entry,
> @@ -102,24 +117,9 @@ void trim_init_extable(struct module *m)
>   */
>  const struct exception_table_entry *
>  search_extable(const struct exception_table_entry *first,
> -           const struct exception_table_entry *last,
> +           const size_t num, 
>             unsigned long value)
>  {
> -    while (first <= last) {
> -        const struct exception_table_entry *mid;
> -
> -        mid = ((last - first) >> 1) + first;
> -        /*
> -         * careful, the distance between value and insn
> -         * can be larger than MAX_LONG:
> -         */
> -        if (ex_to_insn(mid) < value)
> -            first = mid + 1;
> -        else if (ex_to_insn(mid) > value)
> -            last = mid - 1;
> -        else
> -            return mid;
> -    }
> -    return NULL;
> +    return bsearch(&value, first, num, sizeof(struct exception_table_entry), cmp_ex_search);
>  }
>  #endif