linux-toradex.git/lib/sbitmap.c, branch v5.12-rc5

sbitmap: simplify wrap check

2020-12-08T00:12:49+00:00

__sbitmap_get_word() doesn't warp if it's starting from the beginning
(i.e. initial hint is 0). Instead of stashing the original hint just set
@wrap accordingly.

Signed-off-by: Pavel Begunkov 
Signed-off-by: Jens Axboe

sbitmap: replace CAS with atomic and

2020-12-08T00:12:49+00:00

sbitmap_deferred_clear() does CAS loop to propagate cleared bits,
replace it with equivalent atomic bitwise and. That's slightly faster
and makes wait-free instead of lock-free as before.

The atomic can be relaxed (i.e. barrier-less) because following
sbitmap_get*() deal with synchronisation, see comments in
sbitmap_queue_clear().

It's ok to cast to atomic_long_t, that's what bitops/lock.h does.

Signed-off-by: Pavel Begunkov 
Signed-off-by: Jens Axboe

sbitmap: remove swap_lock

2020-12-08T00:12:49+00:00

map->swap_lock protects map->cleared from concurrent modification,
however sbitmap_deferred_clear() is already atomically drains it, so
it's guaranteed to not loose bits on concurrent
sbitmap_deferred_clear().

A one threaded tag heavy test on top of nullbk showed ~1.5% t-put
increase, and 3% -> 1% cycle reduction of sbitmap_get() according to perf.

Signed-off-by: Pavel Begunkov 
Signed-off-by: Jens Axboe

sbitmap: optimise sbitmap_deferred_clear()

2020-12-08T00:12:49+00:00

Because of spinlocks and atomics sbitmap_deferred_clear() have to reload
&sb->map[index] on each access even though the map address won't change.
Pass in sbitmap_word instead of {sb, index}, so it's cached in a
variable. It also improves code generation of
sbitmap_find_bit_in_index().

Signed-off-by: Pavel Begunkov 
Reviewed-by: John Garry 
Signed-off-by: Jens Axboe

sbitmap: Consider cleared bits in sbitmap_bitmap_show()

2020-07-01T16:53:00+00:00

sbitmap works by maintaining separate bitmaps of set and cleared bits.
The set bits are cleared in a batch, to save the burden of continuously
locking the "word" map to unset.

sbitmap_bitmap_show() only shows the set bits (in "word"), which is not
too much use, so mask out the cleared bits.

Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits")
Signed-off-by: John Garry 
Signed-off-by: Jens Axboe

sbitmap: only queue kyber's wait callback if not already active

2019-12-20T23:51:54+00:00

Under heavy loads where the kyber I/O scheduler hits the token limits for
its scheduling domains, kyber can become stuck.  When active requests
complete, kyber may not be woken up leaving the I/O requests in kyber
stuck.

This stuck state is due to a race condition with kyber and the sbitmap
functions it uses to run a callback when enough requests have completed.
The running of a sbt_wait callback can race with the attempt to insert the
sbt_wait.  Since sbitmap_del_wait_queue removes the sbt_wait from the list
first then sets the sbq field to NULL, kyber can see the item as not on a
list but the call to sbitmap_add_wait_queue will see sbq as non-NULL. This
results in the sbt_wait being inserted onto the wait list but ws_active
doesn't get incremented.  So the sbitmap queue does not know there is a
waiter on a wait list.

Since sbitmap doesn't think there is a waiter, kyber may never be
informed that there are domain tokens available and the I/O never advances.
With the sbt_wait on a wait list, kyber believes it has an active waiter
so cannot insert a new waiter when reaching the domain's full state.

This race can be fixed by only adding the sbt_wait to the queue if the
sbq field is NULL.  If sbq is not NULL, there is already an action active
which will trigger the re-running of kyber.  Let it run and add the
sbt_wait to the wait list if still needing to wait.

Reviewed-by: Omar Sandoval 
Signed-off-by: David Jeffery 
Reported-by: John Pittman 
Tested-by: John Pittman 
Signed-off-by: Jens Axboe

sbitmap: Delete sbitmap_any_bit_clear()

2019-11-13T19:50:40+00:00

Since the only caller of this function has been deleted, delete this one
also.

Signed-off-by: John Garry 
Signed-off-by: Jens Axboe

sbitmap: Replace cmpxchg with xchg

2019-07-01T17:57:12+00:00

cmpxchg() with an immediate value could be replaced with less expensive
xchg(). The same true if new value don't _depend_ on the old one.

In the second block, atomic_cmpxchg() return value isn't checked, so
after atomic_cmpxchg() ->  atomic_xchg() conversion it could be replaced
with atomic_set(). Comparison with atomic_read() in the second chunk was
left as an optimisation (if that was the initial intention).

Reviewed-by: Omar Sandoval 
Signed-off-by: Pavel Begunkov 
Signed-off-by: Jens Axboe

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

2019-06-05T15:37:06+00:00

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 v2 as published
  by the free software foundation this program is distributed in the
  hope that it will be useful but without any warranty without even
  the implied warranty of merchantability or fitness for a particular
  purpose see the gnu general public license for more details you
  should have received a copy of the gnu general public license along
  with this program if not see https www gnu org licenses

extracted by the scancode license scanner the SPDX license identifier

  GPL-2.0-only

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

Signed-off-by: Thomas Gleixner 
Reviewed-by: Alexios Zavras 
Reviewed-by: Armijn Hemel 
Reviewed-by: Kate Stewart 
Reviewed-by: Allison Randal 
Cc: linux-spdx@vger.kernel.org
Link: https://lkml.kernel.org/r/20190530000435.923873561@linutronix.de
Signed-off-by: Greg Kroah-Hartman

sbitmap: fix improper use of smp_mb__before_atomic()

2019-05-23T16:25:26+00:00

This barrier only applies to the read-modify-write operations; in
particular, it does not apply to the atomic_set() primitive.

Replace the barrier with an smp_mb().

Fixes: 6c0ca7ae292ad ("sbitmap: fix wakeup hang after sbq resize")
Cc: stable@vger.kernel.org
Reported-by: "Paul E. McKenney" 
Reported-by: Peter Zijlstra 
Signed-off-by: Andrea Parri 
Reviewed-by: Ming Lei 
Cc: Jens Axboe 
Cc: Omar Sandoval 
Cc: Ming Lei 
Cc: linux-block@vger.kernel.org
Cc: "Paul E. McKenney" 
Cc: Peter Zijlstra 
Signed-off-by: Jens Axboe