sbitmap: Use lock/unlock atomic bitops
Subsystems (2)
RFC PATCH 1/1 sbitmap: Use lock/unlock atomic bitops
sbitmap is used to allocate tags. The free and alloc paths use a memory ordering scheme similar to the one used by waitqueue, where the waiter and waker synchronize around set_current_state().
This doesn't seem sufficient for sbitmap given that a tag may get released and re-acquired without the allocator blocking at all. Once the bit for the tag is cleared, the tag may be reused immediately and due to the lack of memory ordering around bit clearing, its memory accesses may race against the ones from before the clearing.
Given that the bits are the primary synchronization mechanism, they should be ordered memory-wise. This patch replaces waitqueue-style memory barriers with clear_bit_unlock() in sbitmap_clear_bit() and test_and_set_bit_lock() in __sbitmap_get_word().
---
Hello,
Spotted this while verifying the timeout fix. I didn't check the whole code, so although unlikely it's possible that the removed mb's are needed from elsewhere, so the RFC. Only boot tested.
Thanks.
include/linux/sbitmap.h | 3 ++- lib/sbitmap.c | 17 ++++++----------- 2 files changed, 8 insertions(+), 12 deletions(-)
include/linux/sbitmap.h +2 -1
@@ -297,7 +297,8 @@ static inline void sbitmap_set_bit(strucstatic inline void sbitmap_clear_bit (struct sbitmap *sb,unsigned int bitnr) { -clear_bit (SB_NR_TO_BIT (sb, bitnr),__sbitmap_word (sb, bitnr)); +/* paired with test_and_set_bit_lock() in __sbitmap_get_word() */ +clear_bit_unlock (SB_NR_TO_BIT (sb, bitnr),__sbitmap_word (sb, bitnr)); }static inline int sbitmap_test_bit (struct sbitmap *sb,unsigned int bitnr)
lib/sbitmap.c +6 -11
@@ -100,7 +100,8 @@ static int __sbitmap_get_word(unsigned lreturn -1 ; } -if (!test_and_set_bit (nr, word)) +/* paired with clear_bit_unlock() in sbitmap_clear_bit() */ +if (!test_and_set_bit_lock (nr, word))break ; hint = nr +1 ;
@@ -432,14 +433,9 @@ static void sbq_wake_up(struct sbitmap_qint wait_cnt;/* -* Pairs with the memory barrier in set_current_state() to ensure the -* proper ordering of clear_bit()/waitqueue_active() in the waker and -* test_and_set_bit()/prepare_to_wait()/finish_wait() in the waiter. See -* the comment on waitqueue_active(). This is __after_atomic because we -* just did clear_bit() in the caller. +* Memory ordering is handled by sbitmap_clear_bit() and +* __sbitmap_get_word(). */ -smp_mb__after_atomic (); - ws =sbq_wake_ptr (sbq);if (!ws)return ;
@@ -481,10 +477,9 @@ void sbitmap_queue_wake_all(struct sbitmint i, wake_index;/* -* Pairs with the memory barrier in set_current_state() like in -* sbq_wake_up(). +* Memory ordering is handled by sbitmap_clear_bit() and +* __sbitmap_get_word(). */ -smp_mb (); wake_index =atomic_read (&sbq->wake_index);for (i =0 ; i <SBQ_WAIT_QUEUES ; i++) {struct sbq_wait_state *ws = &sbq->ws[wake_index];
Quoted 32 lines · Tejun Heo
sbitmap is used to allocate tags. The free and alloc paths use a memory ordering scheme similar to the one used by waitqueue, where the waiter and waker synchronize around
set_current_state().This doesn't seem sufficient for sbitmap given that a tag may get released and re-acquired without the allocator blocking at all. Once the bit for the tag is cleared, the tag may be reused immediately and due to the lack of memory ordering around bit clearing, its memory accesses may race against the ones from before the clearing.
Given that the bits are the primary synchronization mechanism, they should be ordered memory-wise. This patch replaces waitqueue-style memory barriers with
clear_bit_unlock()insbitmap_clear_bit()andtest_and_set_bit_lock()in__sbitmap_get_word().Signed-off-by Tejun Heo <[email protected]>---
Hello,Spotted this while verifying the timeout fix. I didn't check the whole code, so although unlikely it's possible that the removed mb's are needed from elsewhere, so the RFC. Only boot tested.
Thanks.
include/linux/sbitmap.h | 3 ++- lib/sbitmap.c | 17 ++++++----------- 2 files changed, 8 insertions(+), 12 deletions(-)
include/linux/sbitmap.h static inline void sbitmap_set_bit(struc · line 302
Quoted 7 lines
include/linux/sbitmap.h +2
-1@@ -297,7 +297,8 @@ static inline void sbitmap_set_bit(strucstatic inline void sbitmap_clear_bit (struct sbitmap *sb,unsigned int bitnr) { -clear_bit (SB_NR_TO_BIT (sb, bitnr),__sbitmap_word (sb, bitnr)); +/* paired with test_and_set_bit_lock() in __sbitmap_get_word() */ +clear_bit_unlock (SB_NR_TO_BIT (sb, bitnr),__sbitmap_word (sb, bitnr)); }
I agree that we want this, but for a different reason than you described in your changelog: a sbitmap can be used without a sbitmap_queue, so it should provide the proper memory ordering. For the sbitmap_queue case, the compiler/processor could also reorder something after the clear_bit() and before the smp_mb__after_atomic(), which is also wrong.
lib/sbitmap.c static int __sbitmap_get_word(unsigned l · line 105
Quoted 11 lines
include/linux/sbitmap.h +0
-0static inline int sbitmap_test_bit (struct sbitmap *sb,unsigned int bitnr)lib/sbitmap.c +2
-1@@ -100,7 +100,8 @@ static int __sbitmap_get_word(unsigned lreturn -1 ; } -if (!test_and_set_bit (nr, word)) +/* paired with clear_bit_unlock() in sbitmap_clear_bit() */ +if (!test_and_set_bit_lock (nr, word))break ;
test_and_set_bit_lock() is an ACQUIRE operation which has weaker guarantees than the full barrier implied by test_and_set_bit(), but ACQUIRE is enough here, so I agree with this part, too.
Quoted 5 lines
lib/sbitmap.c +0
-0hint = nr +1 ;@@ -432,14 +433,9 @@ static void sbq_wake_up(struct sbitmap_qint wait_cnt;/*
lib/sbitmap.c static void sbq_wake_up(struct sbitmap_q · line 442
Quoted 10 lines
lib/sbitmap.c +2
-7-* Pairs with the memory barrier in set_current_state() to ensure the -* proper ordering of clear_bit()/waitqueue_active() in the waker and -* test_and_set_bit()/prepare_to_wait()/finish_wait() in the waiter. See -* the comment on waitqueue_active(). This is __after_atomic because we -* just did clear_bit() in the caller. +* Memory ordering is handled by sbitmap_clear_bit() and +* __sbitmap_get_word(). */ -smp_mb__after_atomic (); -
This, I'm not convinced that we can get rid of. clear_bit_unlock() is a RELEASE operation, not a full barrier, so the waitqueue_active() read can be reordered before the clear_bit() store. Imagine we get this interleaving:
waitqueue_active() -> false |
| /* bitmap is full, allocation fails */ | prepare_to_wait()clear_bit_unlock() |
We should've woken up the waiter, but we didn't.
lib/sbitmap.c void sbitmap_queue_wake_all(struct sbitm · line 487
Quoted 13 lines
lib/sbitmap.c +2
-3ws =sbq_wake_ptr (sbq);if (!ws)return ;@@ -481,10 +477,9 @@ void sbitmap_queue_wake_all(struct sbitmint i, wake_index;/* -* Pairs with the memory barrier in set_current_state() like in -* sbq_wake_up(). +* Memory ordering is handled by sbitmap_clear_bit() and +* __sbitmap_get_word(). */ -smp_mb ();
Same idea here.
lib/sbitmap.c void sbitmap_queue_wake_all(struct sbitm · line 485
Quoted 3 lines
lib/sbitmap.c +0
-0wake_index =atomic_read (&sbq->wake_index);for (i =0 ; i <SBQ_WAIT_QUEUES ; i++) {struct sbq_wait_state *ws = &sbq->ws[wake_index];
So I think we want a patch for the test_and_set_bit_lock() and clear_bit_unlock(), but the rest should stay as-is.
Hello, Omar.
Quoted 6 lines · Omar Sandoval
lib/sbitmap.c void sbitmap_queue_wake_all(struct sbitm · line 485
Quoted 3 lines
lib/sbitmap.c +0
-0wake_index =atomic_read (&sbq->wake_index);for (i =0 ; i <SBQ_WAIT_QUEUES ; i++) {struct sbq_wait_state *ws = &sbq->ws[wake_index];So I think we want a patch for the
test_and_set_bit_lock()andclear_bit_unlock(), but the rest should stay as-is.
Yeah, that makes sense to me. Would you be interested in updating the patch?
Thanks.
Signature · 1 line
tejun
Quoted 7 lines · Tejun Heo
Hello, Omar.
Quoted 4 lines · Omar Sandoval
Quoted 3 lines
lib/sbitmap.c +0
-0wake_index =atomic_read (&sbq->wake_index);for (i =0 ; i <SBQ_WAIT_QUEUES ; i++) {struct sbq_wait_state *ws = &sbq->ws[wake_index];
Quoted 5 lines
Quoted 2 lines
So I think we want a patch for the
test_and_set_bit_lock()andclear_bit_unlock(), but the rest should stay as-is.Yeah, that makes sense to me. Would you be interested in updating the patch?
Yup, I'll send it up. Thanks, Tejun!