lib/bsearch: Provide __always_inline variant

For code that needs the ultimate performance (it can inline the @cmp
function too) or simply needs to avoid calling external functions for
whatever reaso

lib/bsearch: Provide __always_inline variant

For code that needs the ultimate performance (it can inline the @cmp
function too) or simply needs to avoid calling external functions for
whatever reason, provide an __always_inline variant of bsearch().

[ tglx: Renamed to __inline_bsearch() as suggested by Andy ]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Alexandre Chartre <alexandre.chartre@oracle.com>
Acked-by: Andy Lutomirski <luto@kernel.org>
Link: https://lkml.kernel.org/r/20200505135313.624443814@linutronix.de

show more ...

lib/bsearch: Use generic type for comparator function

Comparator function type, cmp_func_t, is defined in the types.h,
use it in bsearch() and, thus, add more sense to the corresponding
comment in t

lib/bsearch: Use generic type for comparator function

Comparator function type, cmp_func_t, is defined in the types.h,
use it in bsearch() and, thus, add more sense to the corresponding
comment in the code.

Link: http://lkml.kernel.org/r/20191007135656.37734-2-andriy.shevchenko@linux.intel.com

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

show more ...

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 372

Based on 1 normalized pattern(s):

this program is free software you can redistribute it and or modify
it under the terms of th

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 372

Based on 1 normalized pattern(s):

this program is free software you can redistribute it and or modify
it under the terms of the gnu general public license as published by
the free software foundation version 2

extracted by the scancode license scanner the SPDX license identifier

GPL-2.0-only

has been chosen to replace the boilerplate/reference in 135 file(s).

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Reviewed-by: Allison Randal <allison@lohutok.net>
Cc: linux-spdx@vger.kernel.org
Link: https://lkml.kernel.org/r/20190531081036.435762997@linutronix.de
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

show more ...

kprobes: Prohibit probing on bsearch()

Since kprobe breakpoing handler is using bsearch(), probing on this
routine can cause recursive breakpoint problem.

int3
->do_int3()
->ftrace_int3_handler

kprobes: Prohibit probing on bsearch()

Since kprobe breakpoing handler is using bsearch(), probing on this
routine can cause recursive breakpoint problem.

int3
->do_int3()
->ftrace_int3_handler()
->ftrace_location()
->ftrace_location_range()
->bsearch() -> int3

Prohibit probing on bsearch().

Signed-off-by: Andrea Righi <righi.andrea@gmail.com>
Acked-by: Masami Hiramatsu <mhiramat@kernel.org>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>
Cc: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Link: http://lkml.kernel.org/r/154998813406.31052.8791425358974650922.stgit@devbox
Signed-off-by: Ingo Molnar <mingo@kernel.org>

show more ...

lib/bsearch.c: micro-optimize pivot position calculation

There is a slightly faster way (in terms of the number of instructions
being used) to calculate the position of a middle element, preserving

lib/bsearch.c: micro-optimize pivot position calculation

There is a slightly faster way (in terms of the number of instructions
being used) to calculate the position of a middle element, preserving
integer overflow safeness.

./scripts/bloat-o-meter lib/bsearch.o.old lib/bsearch.o.new
add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-24 (-24)
function old new delta
bsearch 122 98 -24

TEST

INT array of size 100001, elements [0..100000]. gcc 7.1, Os, x86_64.

a) bsearch() of existing key "100001 - 2":

BASE
====

$ perf stat ./a.out

Performance counter stats for './a.out':

619.445196 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
133 page-faults:u # 0.215 K/sec
1,949,517,279 cycles:u # 3.147 GHz (83.06%)
181,017,938 stalled-cycles-frontend:u # 9.29% frontend cycles idle (83.05%)
82,959,265 stalled-cycles-backend:u # 4.26% backend cycles idle (67.02%)
4,355,706,383 instructions:u # 2.23 insn per cycle
# 0.04 stalled cycles per insn (83.54%)
1,051,539,242 branches:u # 1697.550 M/sec (83.54%)
15,263,381 branch-misses:u # 1.45% of all branches (83.43%)

0.620082548 seconds time elapsed

PATCHED
=======

$ perf stat ./a.out

Performance counter stats for './a.out':

475.097316 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
135 page-faults:u # 0.284 K/sec
1,487,467,717 cycles:u # 3.131 GHz (82.95%)
186,537,162 stalled-cycles-frontend:u # 12.54% frontend cycles idle (82.93%)
28,797,869 stalled-cycles-backend:u # 1.94% backend cycles idle (67.10%)
3,807,564,203 instructions:u # 2.56 insn per cycle
# 0.05 stalled cycles per insn (83.57%)
1,049,344,291 branches:u # 2208.693 M/sec (83.60%)
5,485 branch-misses:u # 0.00% of all branches (83.58%)

0.475760235 seconds time elapsed

b) bsearch() of un-existing key "100001 + 2":

BASE
====

$ perf stat ./a.out

Performance counter stats for './a.out':

499.244480 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
132 page-faults:u # 0.264 K/sec
1,571,194,855 cycles:u # 3.147 GHz (83.18%)
13,450,980 stalled-cycles-frontend:u # 0.86% frontend cycles idle (83.18%)
21,256,072 stalled-cycles-backend:u # 1.35% backend cycles idle (66.78%)
4,171,197,909 instructions:u # 2.65 insn per cycle
# 0.01 stalled cycles per insn (83.68%)
1,009,175,281 branches:u # 2021.405 M/sec (83.79%)
3,122 branch-misses:u # 0.00% of all branches (83.37%)

0.499871144 seconds time elapsed

PATCHED
=======

$ perf stat ./a.out

Performance counter stats for './a.out':

399.023499 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
134 page-faults:u # 0.336 K/sec
1,245,793,991 cycles:u # 3.122 GHz (83.39%)
11,529,273 stalled-cycles-frontend:u # 0.93% frontend cycles idle (83.46%)
12,116,311 stalled-cycles-backend:u # 0.97% backend cycles idle (66.92%)
3,679,710,005 instructions:u # 2.95 insn per cycle
# 0.00 stalled cycles per insn (83.47%)
1,009,792,625 branches:u # 2530.660 M/sec (83.46%)
2,590 branch-misses:u # 0.00% of all branches (83.12%)

0.399733539 seconds time elapsed

Link: http://lkml.kernel.org/r/20170607150457.5905-1-sergey.senozhatsky@gmail.com
Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

show more ...

lib: reduce the use of module.h wherever possible

For files only using THIS_MODULE and/or EXPORT_SYMBOL, map
them onto including export.h -- or if the file isn't even
using those, then just delete t

lib: reduce the use of module.h wherever possible

For files only using THIS_MODULE and/or EXPORT_SYMBOL, map
them onto including export.h -- or if the file isn't even
using those, then just delete the include. Fix up any implicit
include dependencies that were being masked by module.h along
the way.

Signed-off-by: Paul Gortmaker <paul.gortmaker@windriver.com>

show more ...

lib: Add generic binary search function to the kernel.

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them). Since in my
experien

lib: Add generic binary search function to the kernel.

There a large number hand-coded binary searches in the kernel (run
"git grep search | grep binary" to find many of them). Since in my
experience, hand-coding binary searches can be error-prone, it seems
worth cleaning this up by providing a generic binary search function.

This generic binary search implementation comes from Ksplice. It has
the same basic API as the C library bsearch() function. Ksplice uses
it in half a dozen places with 4 different comparison functions, and I
think our code is substantially cleaner because of this.

Signed-off-by: Tim Abbott <tabbott@ksplice.com>
Extra-bikeshedding-by: Alan Jenkins <alan-jenkins@tuffmail.co.uk>
Extra-bikeshedding-by: André Goddard Rosa <andre.goddard@gmail.com>
Extra-bikeshedding-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Signed-off-by: Alessio Igor Bogani <abogani@kernel.org>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

show more ...