On Wed, Feb 19, 2020 at 6:20 PM Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
>
> On Wed, Feb 19, 2020 at 05:30:25PM +0100, Peter Zijlstra wrote:
>
> > By inlining everything in poke_int3_handler() (except bsearch :/) we can
> > mark the whole function off limits to everything and call it a day. That
> > simplicity has been the guiding principle so far.
> >
> > Alternatively we can provide an __always_inline variant of bsearch().
>
> This reduces the __no_sanitize usage to just the exception entry
> (do_int3) and the critical function: poke_int3_handler().
>
> Is this more acceptible?
Let's say it's more acceptable.
Acked-by: Dmitry Vyukov <dvyukov@xxxxxxxxxx>
I guess there is no ideal solution here.
Just a straw man proposal: expected number of elements is large enough
to make bsearch profitable, right? I see 1 is a common case, but the
other case has multiple entries.
> --- a/arch/x86/kernel/alternative.c
> +++ b/arch/x86/kernel/alternative.c
> @@ -979,7 +979,7 @@ static __always_inline void *text_poke_a
> return _stext + tp->rel_addr;
> }
>
> -static int notrace __no_sanitize patch_cmp(const void *key, const void *elt)
> +static __always_inline int patch_cmp(const void *key, const void *elt)
> {
> struct text_poke_loc *tp = (struct text_poke_loc *) elt;
>
> @@ -989,7 +989,6 @@ static int notrace __no_sanitize patch_c
> return 1;
> return 0;
> }
> -NOKPROBE_SYMBOL(patch_cmp);
>
> int notrace __no_sanitize poke_int3_handler(struct pt_regs *regs)
> {
> @@ -1024,9 +1023,9 @@ int notrace __no_sanitize poke_int3_hand
> * Skip the binary search if there is a single member in the vector.
> */
> if (unlikely(desc->nr_entries > 1)) {
> - tp = bsearch(ip, desc->vec, desc->nr_entries,
> - sizeof(struct text_poke_loc),
> - patch_cmp);
> + tp = __bsearch(ip, desc->vec, desc->nr_entries,
> + sizeof(struct text_poke_loc),
> + patch_cmp);
> if (!tp)
> goto out_put;
> } else {
> --- a/include/linux/bsearch.h
> +++ b/include/linux/bsearch.h
> @@ -4,7 +4,29 @@
>
> #include <linux/types.h>
>
> -void *bsearch(const void *key, const void *base, size_t num, size_t size,
> - cmp_func_t cmp);
> +static __always_inline
> +void *__bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
> +{
> + const char *pivot;
> + int result;
> +
> + while (num > 0) {
> + pivot = base + (num >> 1) * size;
> + result = cmp(key, pivot);
> +
> + if (result == 0)
> + return (void *)pivot;
> +
> + if (result > 0) {
> + base = pivot + size;
> + num--;
> + }
> + num >>= 1;
> + }
> +
> + return NULL;
> +}
> +
> +extern void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp);
>
> #endif /* _LINUX_BSEARCH_H */
> --- a/lib/bsearch.c
> +++ b/lib/bsearch.c
> @@ -28,27 +28,9 @@
> * the key and elements in the array are of the same type, you can use
> * the same comparison function for both sort() and bsearch().
> */
> -void __no_sanitize *bsearch(const void *key, const void *base, size_t num, size_t size,
> - cmp_func_t cmp)
> +void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
> {
> - const char *pivot;
> - int result;
> -
> - while (num > 0) {
> - pivot = base + (num >> 1) * size;
> - result = cmp(key, pivot);
> -
> - if (result == 0)
> - return (void *)pivot;
> -
> - if (result > 0) {
> - base = pivot + size;
> - num--;
> - }
> - num >>= 1;
> - }
> -
> - return NULL;
> + __bsearch(key, base, num, size, cmp);
> }
> EXPORT_SYMBOL(bsearch);
> NOKPROBE_SYMBOL(bsearch);
